Question
给你链表的头结点 head ，请将其按 升序 排列并返回
排序后的链表 。
Example 1:
输入：head = [4,2,1,3] 输出：[1,2,3,4]
Example 2:
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
Example 3:
输入：head = [] 输出：[]
提示：
- 链表中节点的数目在范围 [0, 5 * 104] 内
- -105 <= Node.val <= 105
进阶：
你可以在 O(n log n)
时间复杂度和常数级空间复杂度下，对链表进行排序吗？
前言
147.
对链表进行插入排序使用插入排序的方法对链表进行排序，插入排序的时间复杂度是
，其中 n
是链表的长度。这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到
的 时间复杂度和 的空间复杂度，时间复杂度是
的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是
，其中最适合链表的排序算法是归并排序。
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是
。如果要达到
的空间复杂度，则需要使用自底向上的实现方式。
Approach 1: 自顶向下归并排序
对链表自顶向下归并排序的过程如下。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于
1，即当链表为空或者链表只包含 1
个节点时，不需要对链表进行拆分和排序。
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
| class Solution:
def sortList(self, head: ListNode) -> ListNode:
def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
if not head:
return head
if head.next == tail:
head.next = None
return head
slow = fast = head
while fast != tail:
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
mid = slow
return merge(sortFunc(head, mid), sortFunc(mid, tail))
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
return sortFunc(head, None)
|
复杂度分析
- 时间复杂度：，其中
n 是链表的长度。
- 空间复杂度：，其中 n
是链表的长度。空间复杂度主要取决于递归调用的栈空间。
Approach 2: 自底向上归并排序
使用自底向上的方法实现归并排序，则可以达到 的空间复杂度。
首先求得链表的长度 ，然后将链表拆分成子链表进行合并。
具体做法如下。
将
的值加倍，重复第 2
步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 ，整个链表排序完毕。
如何保证每次合并之后得到的子链表都是有序的呢？可以通过数学归纳法证明。
因此可以保证最后得到的链表是有序的。
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
| class Solution:
def sortList(self, head: ListNode) -> ListNode:
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
if not head:
return head
length = 0
node = head
while node:
length += 1
node = node.next
dummyHead = ListNode(0, head)
subLength = 1
while subLength < length:
prev, curr = dummyHead, dummyHead.next
while curr:
head1 = curr
for i in range(1, subLength):
if curr.next:
curr = curr.next
else:
break
head2 = curr.next
curr.next = None
curr = head2
for i in range(1, subLength):
if curr and curr.next:
curr = curr.next
else:
break
succ = None
if curr:
succ = curr.next
curr.next = None
merged = merge(head1, head2)
prev.next = merged
while prev.next:
prev = prev.next
curr = succ
subLength <<= 1
return dummyHead.next
|
复杂度分析
- 时间复杂度：，其中
n 是链表的长度。
- 空间复杂度：。