143.重排链表

给定一个单链表 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]

示例 2：

img

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

在234.回文链表中，我们实现了找到中点+反转链表+对比的操作，而在143重排链表中，继续使用找到中点+反转链表+链表归并操作

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
63
64
65
66
67
68
69
70
71
72
73
74
// 定义Solution类
class Solution {
    // reorderList方法接收一个链表的头节点head，用于重新排序链表
    public void reorderList(ListNode head) {
        // 如果链表为空，则直接返回
        if (head == null) {
            return;
        }
        // 使用middleNode方法找到链表的中间节点
        ListNode mid = middleNode(head);
        // l1指向链表的第一部分的头节点
        ListNode l1 = head;
        // l2指向链表第二部分的头节点，即中间节点的下一个节点
        ListNode l2 = mid.next;
        // 将链表从中间断开
        mid.next = null;
        // 使用reverseList方法反转链表的第二部分
        l2 = reverseList(l2);
        // 使用mergeList方法将两部分链表交替合并
        mergeList(l1, l2);
    }

    // middleNode方法用于找到链表的中间节点
    public ListNode middleNode(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;
    }

    // reverseList方法用于反转链表
    public ListNode reverseList(ListNode head) {
        // prev用于记录反转后的链表的头节点
        ListNode prev = null;
        // curr指向当前正在处理的节点
        ListNode curr = head;
        while (curr != null) {
            // nextTemp暂存curr的下一个节点
            ListNode nextTemp = curr.next;
            // 将curr的next指向prev，完成反转
            curr.next = prev;
            // prev移动到curr
            prev = curr;
            // curr移动到nextTemp
            curr = nextTemp;
        }
        // 返回反转后的链表的头节点
        return prev;
    }

    // mergeList方法用于交替合并两个链表
    public void mergeList(ListNode l1, ListNode l2) {
        // l1_tmp和l2_tmp用于暂存下一个要处理的节点
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2; // 将l1的next指向l2，实现交替
            l1 = l1_tmp; // 移动l1到下一个原始节点

            l2.next = l1; // 将l2的next指向l1，继续交替
            l2 = l2_tmp; // 移动l2到下一个反转后的节点
        }
    }
}