148. Sort List

, ,

MergeSort

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
class Solution {
    public ListNode sortList(ListNode head) {
        // 不要忘记递归终止条件
        if (head == null || head.next == null) {
            return head;
        }

        // d -> h -> 1
        //           f
        //      s

        // d -> h -> 1 -> 2    
        //                     f
        //           s

        ListNode fast = head, slow = new ListNode(-1, head);

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode rightHead = slow.next;
        slow.next = null;

        ListNode orderedHeadA = sortList(head);
        ListNode orderedHeadB = sortList(rightHead);

        // merge
        ListNode dummyHead = new ListNode();
        ListNode pre = dummyHead, nodeA = orderedHeadA, nodeB = orderedHeadB;
        while (nodeA != null && nodeB != null) { // 注意合并时的细节
            if (nodeA.val <= nodeB.val) {
                pre.next = nodeA;
                nodeA = nodeA.next;
            } else {
                pre.next = nodeB;
                nodeB = nodeB.next;
            }
            pre = pre.next;
        }
        pre.next = nodeA != null ? nodeA : nodeB; // 不要忘记剩余的节点

        return dummyHead.next;
    }
}

MergeSort

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
75
76
77
78
79
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        int length = getLength(head);

        for (int pieceLength = 1; pieceLength < length; pieceLength *= 2) {
            ListNode pre = dummyHead;
            ListNode curr = pre.next; // 注意每轮的起点为 pre.next, 不能为 head, 因为 head 可能被交换到后面去了


            while (curr != null) { // 不要忘记这一层循环，因为一个链表中可能存在多对左右链表
                int i = pieceLength;
                ListNode l1 = curr;
                while (curr != null && i > 0) {
                    curr = curr.next;
                    i--;
                }

                if (i > 0) {
                    // 左侧的子链表元素个数不足 pieceLength 个，即不能构成左链表与右链表，无需执行下面的归并左右链表的逻辑，此时直接跳出 for 循环，如果 i 等于 0 说明当前节点位于右侧子链表的首个节点，需要归并排序
                    break;
                }

                ListNode l2 = curr;
                i = pieceLength;
                while (curr != null && i > 0) {
                    curr = curr.next;
                    i--;
                }

                ListNode nextPairStartNode = curr;

                int l1Length = pieceLength, l2Length = pieceLength - i; // 到此处时 l1 长度肯定为 pieceLength, l2 则为 pieceLength - i
                // 根据左右子链表的长度进行归并，注意不能使用 next, 因为我们没有将两个子链表切断
                while (l1Length > 0 && l2Length > 0) {
                    if (l1.val < l2.val) {
                        pre.next = l1;
                        l1 = l1.next;
                        l1Length--;
                    } else {
                        pre.next = l2;
                        l2 = l2.next;
                        l2Length--;
                    }
                    pre = pre.next;
                }

                // 当两个子链表长度不等时处理较长的链表部分
                pre.next = l1Length > 0 ? l1 : l2;
                // 将 pre 继续在子链表上移动，移动至子链表的尾节点
                while (l1Length > 0 || l2Length > 0) {
                    pre = pre.next;
                    l1Length--;
                    l2Length--;
                }

                // 当前 pre 指向的合并后的链表的尾节点，注意该节点可能含有 next 指针，所以我们校正该 next 指针指向下一对链表的头节点
                pre.next = nextPairStartNode;
            }
        }

        return dummyHead.next;
    }

    private int getLength(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }
}

迭代法细节较多，想一次写对还是比较困难。

References

148. Sort List
剑指 Offer II 077. 链表排序