LeetCode 328. 奇偶链表

Categories:

题目描述
思路分析
1. 解法一：双指针分离奇偶链表（推荐）
相似题目

题目描述

✅ 328. 奇偶链表

思路分析

解法一：双指针分离奇偶链表（推荐）

核心思路：

使用两个指针 odd 和 even 分别维护奇数位链表和偶数位链表的尾节点。

odd 从第 1 个节点出发，even 从第 2 个节点出发，额外记录偶数链表头 evenHead 供最后拼接使用。

每次迭代：odd.next 跳过当前偶数节点指向下一个奇数节点，even.next 跳过新 odd 指向下一个偶数节点，两指针同步前进。

循环终止条件：even == null 或 even.next == null（链表已遍历完毕）。

最后将奇数链表尾部连接到 evenHead，完成两段链表的拼接。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表的节点总数，每个节点只访问一次。

空间复杂度：O(1)，只使用了常数个额外指针变量。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // odd 指向奇数链表当前尾节点，even 指向偶数链表当前尾节点
        ListNode odd = head;
        ListNode even = head.next;
        // 记录偶数链表头，最终拼接使用
        ListNode evenHead = even;
        while (even != null && even.next != null) {
            // 奇数指针跳过当前偶数节点，指向下一个奇数节点
            odd.next = even.next;
            odd = odd.next;
            // 偶数指针跳过当前奇数节点，指向下一个偶数节点
            even.next = odd.next;
            even = even.next;
        }
        // 将奇数链表尾部连接到偶数链表头部
        odd.next = evenHead;
        return head;
    }
}

func oddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // odd 指向奇数链表当前尾节点，even 指向偶数链表当前尾节点
    odd := head
    even := head.Next
    // 记录偶数链表头，最终拼接使用
    evenHead := even
    for even != nil && even.Next != nil {
        // 奇数指针跳过当前偶数节点，指向下一个奇数节点
        odd.Next = even.Next
        odd = odd.Next
        // 偶数指针跳过当前奇数节点，指向下一个偶数节点
        even.Next = odd.Next
        even = even.Next
    }
    // 将奇数链表尾部连接到偶数链表头部
    odd.Next = evenHead
    return head
}

相似题目

题目	难度	考察点
206. 反转链表	简单	链表 / 双指针
92. 反转链表 II	中等	链表 / 区间反转
86. 分隔链表	中等	链表 / 按条件分割
148. 排序链表	中等	链表 / 归并排序
143. 重排链表	中等	链表 / 找中点 + 反转 + 合并
21. 合并两个有序链表	简单	链表 / 双指针合并
19. 删除链表的倒数第 N 个结点	中等	链表 / 快慢指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/54921733