148. 排序链表(Medium)
# 题目描述
给你链表的头结点 head
,请将其按 升序 排列并返回 排序后的链表 。
# 样例
Input: [4,2,1,3]
Output: [1,2,3,4]
1
2
2
# 题解
归并算法 = 有序链表合并 + 分治 + 快慢指针找中点
# Python示例
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
def mergeTwoList(l1, l2): # 有序链表合并
if not l1: return l2
if not l2: return l1
dummpyHead = ListNode(None)
p = dummpyHead
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l1 if l1 else l2
return dummpyHead.next
if not head or not head.next: return head
# 找中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# 分治
left, right = self.sortList(head), self.sortList(mid)
return mergeTwoList(left, right)
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
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
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54