148. Sort List
Sort a linked list in time using constant space complexity.
Solution: Merge Sort
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
middle = self.get_middle(head)
right = middle.next
middle.next = None
left = self.sortList(head)
right = self.sortList(right)
return self.merge(left, right)
def get_middle(self, head):
if not head or not head.next:
return head
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def merge(self, left, right):
cur = dummy = ListNode(None)
while left and right:
if left.val < right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
if left:
cur.next = left
if right:
cur.next = right
return dummy.next