排序链表

问题陈述

思路分析

递归实现链表归并排序

1、分割

找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；

  • 我们使用 fast,slow 快慢双指针法，链表有奇数个节点找到中点，偶数个节点找到中心左边的节点。
  • 找到中点 slow 后，执行 slow.next = None 将链表切断。
  • 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
  • cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。

2、合并

将两个排序链表合并，转化为一个排序链表

  • 双指针法合并，建立辅助ListNode h 作为头部。
  • 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
  • 返回辅助ListNode h 作为头部的下个节点 h.next。
  • 时间复杂度 O(l + r)，l, r 分别代表两个链表长度。

代码实现

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
class Solution{
    public ListNode sortList(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        
        ListNode tmp=slow.next;
        slow.next=null;
        ListNode left=sortList(head);
        ListNode right=sortList(tmp);
        ListNode h=new ListNode(0);
        ListNode res=h;
        if(left!=null&& right!=null){
            if(left.val<right.val){
                h.next=left;
                left=left.next;
            }else{
                h.next=right;
                right=right.next;
            }
            h=h.next;
        }
        h.next=left==null?right:left;
        return res.next;
    }
}

快速排序

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
public class LeetCode_00148 {

    /**
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(logn)
     * @param head 待排序链表头结点
     * @return 排序后链表的头结点
     */
    public ListNode sortList(ListNode head) {
        quickSort(head, null);
        return head;
    }

    /**
     * 对区间 [head, end) 排序
     * @param head 链表头结点
     * @param end 链表尾结点（不包含）
     */
    private void quickSort(ListNode head, ListNode end) {
        if (head != end) {
            ListNode q = partition(head, end);
            quickSort(head, q);
            quickSort(q.next, end);
        }
    }

    private ListNode partition(ListNode head, ListNode end) {//将
        int x = head.val;
        // p 代表小于 x 的最后一个结点
        ListNode p = head;
        ListNode q = head.next;
        while (q != end) {
            if (q.val < x) {
                p = p.next;
                swap(p, q);
            }
            q = q.next;
        }
        swap(head, p);
        return p;
    }

    private void swap(ListNode p, ListNode q) {
        int tmp = p.val;
        p.val = q.val;
        q.val = tmp;
    }
}

归并排序

  • 当初始化fast = head; slow = head时，运用快慢指针方法最后两个指针的指向情况如下：
    • 当链表长度为奇数时，fast 指向尾结点，slow 指向中心结点。
    • 当链表长度为偶数时，fast 指向 null，slow 指向下中位数结点。
  • 当初始化fast = head.next; slow = head时，运用快慢指针方法最后两个指针的指向情况如下：
    • 当链表长度为奇数时，fast 指向尾结点，slow 指向中心结点。
    • 当链表长度为偶数时，fast 指向尾结点，slow 指向上中位数结点。
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
public class LeetCode_00148 {

    /**
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(logn)
     * 不用额外创建数组，空间复杂度降低了，链表排序的最佳方法
     *
     * @param head 待排序链表头结点
     * @return 排序后链表的头结点
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        ListNode a = sortList(head);
        ListNode b = sortList(fast);
        return mergeList(a, b);
    }

    private ListNode mergeList(ListNode a, ListNode b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.val < b.val) {
            a.next = mergeList(a.next, b);
            return a;
        } else {
            b.next = mergeList(a, b.next);
            return b;
        }
    }
}

由于题目要求空间复杂度为 O(1)，应该使用自底向上的归并排序。

“自顶向下”的归并排序。
该类归并排序是算法设计中“分治”思想的典型应用。
其实就是将数组分为两部分，然后递归地将两部分分别排序，将排序后的两个数组进行归并。

“自底向上”的归并排序。
该类归并排序是先两两归并size=1的小数组，形成size=2的各对数组；然后再两两归并size=2数组，直到归并size=N的大数组。
“自底向上”不需要用到递归，适合以链表形式组织的数据。

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
public class LeetCode_00148 {
    /**
     * 自底向上的归并排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     *
     * @param head 待排序链表头结点
     * @return 排序后链表的头结点
     */
    public ListNode sortList(ListNode head) {
        int n = 0;
        for (ListNode p = head; p != null; p = p.next) {
            ++n;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        for (int i = 1; i < n; i <<= 1) {
            ListNode cur = dummy;
            for (int j = 0; j + i < n; j += i << 1) {
                ListNode a = cur.next, b = cur.next;
                for (int k = 0; k < i; ++k) {
                    b = b.next;
                }
                int l = 0, r = 0;
                while (l < i && r < i && b != null) {
                    if (a.val < b.val) {
                        cur.next = a;
                        cur = a;
                        a = a.next;
                        ++l;
                    } else {
                        cur.next = b;
                        cur = b;
                        b = b.next;
                        ++r;
                    }
                }
                while (l < i) {
                    cur.next = a;
                    cur = a;
                    a = a.next;
                    ++l;
                }
                while (r < i && b != null) {
                    cur.next = b;
                    cur = b;
                    b = b.next;
                    ++r;
                }
                cur.next = b;
            }
        }
        return dummy.next;
    }
}