148. 排序链表

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表

输入输出

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

输入：head = []
输出：[]

基本思路

方法一：自顶向下的归并排序

  1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
  2. 对两个子链表分别排序。
  3. 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
  4. 时复$O(nlogn)$ 空复$O(n)$(因为递归调用栈)

方法二：自底向上的归并排序

  1. 用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1。
  2. 每次将链表拆分成若干个长度为subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。
  3. 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。
  4. 时复$O(nlogn)$ 空复$O(1)$

java实现

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 方法一
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail){
        if(head == null) return head;
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while(fast != tail){
            slow = slow.next;
            fast = fast.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = mergeTwoList(list1, list2);
        return sorted;
    }

    public ListNode mergeTwoList(ListNode p1, ListNode p2){
        // 合并两个有序链表
        ListNode dummyNode = new ListNode(0);
        ListNode temp = dummyNode, temp1 = p1, temp2 = p2;
        while(temp1 != null && temp2 != null){
            if(temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if(temp1 != null){
            temp.next = temp1;
        }else if(temp2 != null){
            temp.next = temp2;
        }
        return dummyNode.next;
    }
}

// 方法二
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null) return head;
        
        //1.统计链表长度
        int length = 0;
        ListNode node = head;
        while(node != null){
            length++;
            node = node.next;
        }
        
        //2.初始化 引入dummyNode
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        //3.每次将链表拆分成若干个长度为subLen的子链表，并按照每两个子链表一组进行合并，sublen每次乘以2
        for(int sublen = 1; sublen < length; sublen <<= 1){
            ListNode pre = dummyNode;
            ListNode cur = dummyNode.next;
            while(cur != null){
                //3.1拆分sublen长度的链表成第一段
                ListNode head_1 = cur;
                for(int i = 1; i < sublen && cur != null && cur.next != null; i++){
                    cur = cur.next;
                }

                //3.2拆分sublen长度的链表成第二段
                ListNode head_2 = cur.next;
                cur.next = null;
                cur = head_2;
                for(int i = 1; i < sublen && cur != null && cur.next != null; i++){
                    cur = cur.next;
                }

                //3.3断开 第二个链表后边的节点为next
                ListNode next = null;
                if(cur != null){
                    next = cur.next;
                    cur.next = null;
                }

                //3.4两个sublen长度的链表合并 pre连接merge后的链表头部
                ListNode merged = mergeTwoList(head_1, head_2);
                pre.next = merged;
                //pre移动到merge后的链表后边
                while(pre.next != null){
                    pre = pre.next;
                }
                //next用来记录拆分完两个链表的结束位置
                cur = next;
            }
        }
        return dummyNode.next;
    }

    public ListNode mergeTwoList(ListNode p1, ListNode p2){
        // 合并两个有序链表
        ListNode dummyNode = new ListNode(0);
        ListNode temp = dummyNode, temp1 = p1, temp2 = p2;
        while(temp1 != null && temp2 != null){
            if(temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if(temp1 != null){
            temp.next = temp1;
        }else if(temp2 != null){
            temp.next = temp2;
        }
        return dummyNode.next;
    }
}