题目描述:
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
示例 1:
输入:head = [4,2,1,3]
输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]
示例 3:
输入:head = []
输出:[]
提示:
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗
解题思路一:递归的归并排序,两个关键点,找到中点mid和分割链表。前者通过快慢指针,后者通过指向None。即mid, slow.next = slow.next, None
然后对分割的链表再次进行递归分割,直到满足终止条件if not head or not head.next:
最后进行归并排序:空间复杂度:O(logn)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: # termination.
return head
slow, fast = head, head.next
while fast and fast.next:
fast, slow = fast.next.next, slow.next
mid, slow.next = slow.next, None # mid 奇数个节点找到中点右边,偶数个节点找到中心右边的节点。slow.next = None 分割链表
left, right = self.sortList(head), self.sortList(mid) # 递归分割
h = res = ListNode(0)
while left and right: # 归并排序
if left.val < right.val:
h.next, left = left, left.next
else:
h.next, right = right, right.next
h = h.next
h.next = left if left else right
return res.next
时间复杂度:O(nlogn)
空间复杂度:O(logn)
解题思路二:归并排序(从底至顶直接合并)非递归
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
h, length, intv = head, 0, 1
while h: h, length = h.next, length + 1
res = ListNode(0)
res.next = head
# merge the list in different intv.
while intv < length:
pre, h = res, res.next
while h:
# get the two merge head `h1`, `h2`
h1, i = h, intv
while i and h: h, i = h.next, i - 1
if i: break # no need to merge because the `h2` is None.
h2, i = h, intv
while i and h: h, i = h.next, i - 1
c1, c2 = intv, intv - i # the `c2`: length of `h2` can be small than the `intv`.
# merge the `h1` and `h2`.
while c1 and c2:
if h1.val < h2.val: pre.next, h1, c1 = h1, h1.next, c1 - 1
else: pre.next, h2, c2 = h2, h2.next, c2 - 1
pre = pre.next
pre.next = h1 if c1 else h2
while c1 > 0 or c2 > 0: pre, c1, c2 = pre.next, c1 - 1, c2 - 1
pre.next = h
intv *= 2
return res.next
详见https://leetcode.cn/problems/sort-list/solutions/13728/sort-list-gui-bing-pai-xu-lian-biao-by-jyd
时间复杂度:O(nlogn)
空间复杂度:O(1)
解题思路三:0
时间复杂度:O(n)
空间复杂度:O(n)