重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1
L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

img

1
2
输入：head = [1,2,3,4]
输出：[1,4,2,3]

快慢指针 （切成两半）+ 反转 + 交替合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // 1. 找到左半部分的尾节点（中点）
        ListNode mid = findMiddle(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null; // 关键：必须断开左右两条链表，否则会形成环！
    
        // 2. 反转右半部分链表
        l2 = reverseList(l2);
    
        // 3. 交替合并 l1 和 l2
        mergeList(l1, l2);
    }
    
    // 步骤 1：快慢指针找中点
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    // 步骤 2：原地反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
    
    // 步骤 3：交替合并两个链表
    private void mergeList(ListNode l1, ListNode l2) {
        ListNode l1Temp;
        ListNode l2Temp;
        while (l1 != null && l2 != null) {
            // 暂存两边的下一个节点
            l1Temp = l1.next;
            l2Temp = l2.next;
    
            // 交错穿插连接
            l1.next = l2;
            l1 = l1Temp;
    
            l2.next = l1;
            l2 = l2Temp;
        }
    }

}