问题描述

给定单链表的头节点 head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点索引为奇数，第二个节点为偶数，以此类推。

解题思路

本题要求就地重新排列链表，将奇数位置（1, 3, 5, …）的节点放在前面，偶数位置（2, 4, 6, …）的节点放在后面，且保持各自的相对顺序。

双指针分离法

使用两个指针 odd 和 even 分别追踪奇数和偶数链表的尾节点：

  1. 初始化：

    • odd 指向头节点（第 1 个节点，奇数位）
    • even 指向第二个节点（第 2 个节点，偶数位）
    • evenHead 保存偶数链表的头节点，用于最后拼接

  2. 交替跳转：在循环中，每次操作两个节点：

    • odd.next = even.next：将当前奇数节点的 next 跳过偶数节点，连接到下一个奇数节点
    • odd = odd.next：odd 指针移动到下一个奇数节点
    • even.next = odd.next：将当前偶数节点的 next 跳过新奇数节点，连接到下一个偶数节点
    • even = even.next：even 指针移动到下一个偶数节点

  3. 终止条件：当 even == null（偶数节点已用完）或 even.next == null（没有更多奇数节点）时停止。

  4. 拼接：将奇数链表的尾部 odd.next 连接到偶数链表的头部 evenHead，完成拼接。

举例说明

以链表 1 -> 2 -> 3 -> 4 -> 5 为例：

步骤 odd 链表 even 链表 说明
初始 1 -> 2 -> 3 -> 4 -> 5 2 -> 3 -> 4 -> 5 odd=1, even=2, evenHead=2
第1轮 1 -> 3 -> 4 -> 5 2 -> 4 -> 5 odd.next=3, odd移向3; even.next=4, even移向4
第2轮 1 -> 3 -> 5 2 -> 4 odd.next=5, odd移向5; even.next=null, even移向null
终止 even=null，停止
拼接 1 -> 3 -> 5 -> 2 -> 4 odd.next = evenHead

为什么这样做是正确的？

每次迭代中，我们分别将当前奇数节点连接到”隔一个”的下一个奇数节点，当前偶数节点连接到”隔一个”的下一个偶数节点。这样就同时维护了两条独立链表：

  • 奇数链表包含所有奇数位置的节点：1 → 3 → 5 → …
  • 偶数链表包含所有偶数位置的节点：2 → 4 → 6 → …

最后只要把奇数链表的末尾连接到偶数链表的头部即可。

复杂度分析

  • 时间复杂度：O(n)，需要遍历整个链表一次。
  • 空间复杂度：O(1)，只使用了有限的额外指针变量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package code.J328;

import datastructure.ListNode;

public class J328 {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        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;
    }
}