Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
思路
- 归并排序
def sortList(self, head: ListNode) -> ListNode:
def mergeTwoList(L1, L2):
if not L1:
return L2
if not L2:
return L1
newHead = ListNode(0)
L3 = newHead
while L1 and L2:
if L1.val < L2.val:
L3.next = L1
L1 = L1.next
else:
L3.next = L2
L2 = L2.next
L3 = L3.next
if L1:
L3.next = L1
else:
L3.next = L2
return newHead.next
if not head or not head.next:
return head
slow = head
quick = head
while quick.next and quick.next.next:
slow = slow.next
quick = quick.next.next
right = slow.next
slow.next = None
left = self.sortList(head)
right = self.sortList(right)
return mergeTwoList(left, right)
- 快排
def sortList2(self, head: ListNode) -> ListNode:
def partition(head, end):
if not head or not end or head == end:
return
l1 = head
l2 = head.next
pivot = head.val
while l2 != end.next and l2:
if l2.val < pivot:
l1 = l1.next
if l1 != l2:
tmp = l1.val
l1.val = l2.val
l2.val = tmp
l2 = l2.next
if head != l1:
tmp = l1.val
l1.val = head.val
head.val = tmp
return l1
def sortHelper(head, end):
if not head or not end or head == end:
return
node = partition(head, end)
sortHelper(head, node)
sortHelper(node.next, end)
return head
if not head or not head.next:
return head
end = head
while end.next:
end = end.next
new_head = sortHelper(head, end)
return new_head
