題目
給你鏈表的頭結(jié)點(diǎn) head ，請(qǐng)將其按升序排列并返回排序后的鏈表角骤。
例：
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]
方法一：自頂向下歸并排序
sort 函數(shù)：不斷將鏈表一分為二
- head 表示鏈表的頭結(jié)點(diǎn)隅忿，tail 表示鏈表的尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
- 若鏈表無(wú)結(jié)點(diǎn)，那么終止本次拆分鏈表
- 若鏈表只有一個(gè)結(jié)點(diǎn)，那么終止本次拆分鏈表背桐，并將該結(jié)點(diǎn)的后繼結(jié)點(diǎn)設(shè)為空
- slow 和 fast 表示兩個(gè)指針优烧，slow 每次走一步，fast 每次走兩步
- 循環(huán)直至快指針 fast 等于 tail
- 快慢指針均后移一步链峭，并判斷快指針此時(shí)是否位于 tail
- 若并未走至鏈表結(jié)尾畦娄，那么繼續(xù)后移一步
- 快慢指針均后移一步链峭，并判斷快指針此時(shí)是否位于 tail
- mid 表示鏈表的中間結(jié)點(diǎn)，根據(jù)上述快慢指針的移動(dòng)熏版，此時(shí)慢指針 slow 即位于中間結(jié)點(diǎn)纷责，賦值
- 返回兩個(gè)鏈表繼續(xù)拆并分合并后新鏈表
merge 函數(shù)：根據(jù)每個(gè)結(jié)點(diǎn)值大小對(duì)兩個(gè)鏈表合并
思路同 21. 合并兩個(gè)有序鏈表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def sortList(self, head):
def sort(head, tail):
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(sort(head, mid), sort(mid, tail))
def merge(list1, list2):
result = curr = ListNode()
while list1 and list2:
if list1.val <= list2.val:
curr.next = ListNode(list1.val)
list1 = list1.next
else:
curr.next = ListNode(list2.val)
list2 = list2.next
curr = curr.next
if list1:
curr.next = list1
else:
curr.next = list2
return result.next
return sort(head, None)
※
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(logn)
相關(guān)知識(shí)
-
歸并排序：
參考
代碼相關(guān)：https://leetcode.cn/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
歸并排序：https://www.cnblogs.com/chengxiao/p/6194356.html
