leetcode148：排序链表

题目链接

leetcode

题目描述

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

C++ 代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        if (head->next != nullptr) cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    自顶向下归并排序

    1.找到链表的中点，以中点为分界，将链表拆分成两个子链表。
        寻找链表的中点：用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步。
        当快指针到达链表末尾时，慢指针指向的链表结点即为链表的中点。
    2.对两个子链表分别排序。
    3.将两个排序后的子链表合并，得到完整的排序后的链表。
        使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
    上述过程可以通过递归实现。递归的终止条件是链表的结点个数小于或等于 1。

    时间复杂度：O(nlogn)
        其中 n 是链表的结点个数
    空间复杂度：O(logn)
        在最坏情况下，递归调用的栈深度为 logn
*/
class Solution_0 {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }

    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == nullptr) {
            return head;
        }
        if (head->next == tail) {
            head->next = nullptr;
            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;
        return mergeTwoList(sortList(head, mid), sortList(mid, tail));
    }
    
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *p = dummy;
        ListNode *p1 = l1, *p2 = l2;

        while (p1 && p2) {
            // 比较 p1 和 p2 两个指针
            if (p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        // if (p1) cur->next = p1;
        // if (p2) cur->next = p2;
        p->next = (p1 ? p1 : p2);
        return dummy->next;
    }
};

/*
    思路同上
*/ 
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }

    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == nullptr) {
            return head;
        }
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }

        ListNode* mid = getMidNode(head, tail);
        return mergeTwoList(sortList(head, mid), sortList(mid, tail));
    }

    ListNode* getMidNode(ListNode* head, ListNode* tail) {
        ListNode* slow = head, *fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }
        
        return slow;
    } 
    
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *p = dummy;
        ListNode *p1 = l1, *p2 = l2;

        while (p1 && p2) {
            // 比较 p1 和 p2 两个指针
            if (p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        p->next = (p1 ? p1 : p2);
        return dummy->next;
    }
};

/*
    自底向上归并排序

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

    如何保证每次合并之后得到的子链表都是有序的呢？
    可以通过数学归纳法证明。因此，保证最后得到的链表是有序的。

    时间复杂度：O(nlog⁡n)
        其中 n 是链表的长度。
    空间复杂度：O(1)
*/
class Solution_2 {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }

        int length = 0;
        ListNode* node  = head;
        while (node != nullptr) {
            length ++;
            node = node->next;
        }

        ListNode* dummy = new ListNode(-1, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode *prev = dummy, *cur = dummy->next;
            while (cur != nullptr) {
                ListNode* head1 = cur;
                for (int i = 1; i < subLength && cur->next != nullptr; i ++) {
                    cur = cur->next;
                }

                ListNode* head2 = cur->next;
                cur->next = nullptr;
                cur = head2;
                for (int i = 1; i < subLength && cur != nullptr && cur->next != nullptr; i ++) {
                    cur = cur->next;
                }

                ListNode* next = nullptr;
                if (cur != nullptr) {
                    next = cur->next;
                    cur->next = nullptr;
                }
                
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                cur = next;
            }
        }
        
        return dummy->next;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummy = new ListNode(-1);
        ListNode *cur = dummy, *l1 = head1, *l2 = head2;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1 != nullptr) {
            cur->next = l1;
        } else if (l2 != nullptr) {
            cur->next = l2;
        }

        return dummy->next;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {4, 2, 1, 3};

    // 创建链表
    ListNode* head = createList(nums);

    // 排序操作
    ListNode* result = solution.sortList(head);
    // 打印结果
    cout << "Sorted List: ";
    printList(result);

    // 释放内存
    deleteList(result);

    return 0;
}

Golang 代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

func mergeTwoList(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    p, p1, p2 := dummy, l1, l2
    for p1 != nil && p2 != nil {
        if p1.Val <= p2.Val {
            p.Next = p1
            p1 = p1.Next
        } else {
            p.Next = p2
            p2 = p2.Next
        }
        p = p.Next
    }

    if p1 != nil {
        p.Next = p1
    } else if p2 != nil {
        p.Next = p2
    }

    return dummy.Next
}

/*
    基本思路：
        采用归并排序的思想
        1.通过快慢指针将链表分成两部分。
        2.对分开的两部分链表分别递归地进行排序。
        3.将已排序的两部分链表合并。

    时间复杂度：O(nlogn)
        其中 n 是链表的节点个数。
        每次将链表一分为二，然后合并，总共需要 logn 次分解，每次合并操作的时间复杂度为 O(n)。
    空间复杂度：O(logn)
        主要是递归调用栈的空间消耗，递归的深度最大为 logn。
*/
func sortList_0(head *ListNode) *ListNode {
    return sort(head, nil)
}

// 对链表进行排序的函数
// 备注：Golang 没有重载函数，需要根据函数的特征来命名。
func sort(head, tail *ListNode) *ListNode {
    if head == nil {
        return head
    }
    if head.Next == tail {
        head.Next = nil
        return head
    }

    // 快慢指针找到链表的中间节点
    slow, fast := head, head
    for fast != tail {
        slow = slow.Next
        fast = fast.Next
        if fast != tail {
            fast = fast.Next
        }
    }

    mid := slow
    return mergeTwoList(sort(head, mid), sort(mid, tail));
}

/*
    自底向上归并排序
    使用自底向上的方法实现归并排序，可以达到 O(1) 的空间复杂度。

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

    如何保证每次合并之后得到的子链表都是有序的呢？
    可以通过数学归纳法证明。因此，保证最后得到的链表是有序的。

    时间复杂度：O(nlog⁡n)
        其中 n 是链表的长度。
    空间复杂度：O(1)
*/
func sortList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    length := 0
    for node := head; node != nil; node = node.Next {
        length ++
    }

    dummy := &ListNode{Next: head}
    for subLength := 1; subLength < length; subLength <<= 1 {
        prev, cur := dummy, dummy.Next
        for cur != nil {
            head1 := cur
            for i := 1; i < subLength && cur.Next != nil; i ++ {
                cur = cur.Next
            }

            head2 := cur.Next
            cur.Next = nil
            cur = head2
            for i := 1; i < subLength && cur != nil && cur.Next != nil; i ++ {
                cur = cur.Next
            }

            var next *ListNode
            if cur != nil {
                next = cur.Next
                cur.Next = nil
            }

            prev.Next = mergeTwoList(head1, head2)
            for prev.Next != nil {
                prev = prev.Next
            }
            cur = next
        }
    }

    return dummy.Next
}

func main() {
    // 测试用例
    testCases := []struct {
        values   []int
        expected []int
    }{
        {
            values:   []int{4,2,1,3},
            expected: []int{1,2,3,4},
        },
        {
            values:   []int{-1,5,3,4,00},
            expected: []int{-1,0,3,4,5},
        },
        {
            values:   []int{},
            expected: []int{},
        },
    }

    for i, tc := range testCases {
        head := createLinkedList(tc.values)
		fmt.Printf("Test Case %d, Input: head = %v\n", i+1, printLinkedList(head))
        result := sortList(head)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}
#leetcode
leetcode148：排序链表
https://lcf163.github.io/2024/04/14/leetcode148：排序链表/
作者
乘风的小站
发布于
2024年4月14日
许可协议