1.題目
在 O(n log n) 時間復(fù)雜度和常數(shù)級空間復(fù)雜度下，對鏈表進(jìn)行排序痊剖。
示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
2.分析
遞歸排序三部曲：1嘹狞，快慢指針找中點(diǎn)打厘；2望伦，遞歸調(diào)用mergeSort，3古程，合并兩個鏈表
3.解答
一種解答蔼卡，我還沒搞清楚，挣磨，雇逞，，
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head):
"""
主要是使用歸并的思路 先分再合
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
return self.minute(head)
def minute(self, head):
"""
這個方法主要是實(shí)現(xiàn)分的操作
分的過程用快慢指針實(shí)現(xiàn)
:param head:
:return:
"""
if head.next is None:
return head
quick, slow, temp = head, head, head
while quick is not None and quick.next is not None:
temp = slow
slow = slow.next
quick = quick.next.next
temp.next = None # 這一步就是將整個鏈表從中間分開 失去這一步 后面將無限循環(huán)
i = self.minute(head)
j = self.minute(slow)
return self.Combined(i, j)
def Combined(self, i, j):
"""
這個方法主要實(shí)現(xiàn)合的操作
合的過程就是從i 和 j開始比較 就是從開頭和中間開始比較 將兩個相比小的排在head后
最后返回head即可
:param i:ListNode
:param j:ListNode
:return:
"""
TempNode = ListNode(0)
temp = TempNode
while i is not None and j is not None:
if i.val <= j.val:
temp.next = i
i = i.next
else:
temp.next = j
j = j.next
temp = temp.next
if i is not None:
temp.next = i
if j is not None:
temp.next = j
return TempNode.next
