https://leetcode.com/problems/sort-list/
Sort List
Total Accepted: 54042 Total Submissions: 237747 Difficulty: Medium
Sort a linked list in O(n log n) time using constant space complexity.
Code:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
slow= head
fast = head.next
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
s2 = self.sortList(slow.next)
slow.next = None
s1 = self.sortList(head)
return self.merge(s1, s2)
def merge(self, left, right):
head = ListNode(0)
c = head
while left and right:
if right.val < left.val:
c.next = right
c = right
right = right.next
else:
c.next = left
c = left
left = left.next
while left:
c.next = left
c = left
left = left.next
while right:
c.next = right
c = right
right = right.next
return head.next
Idea:
Essentially, it is a merge sort. And we apply the same idea as seen in Find LinkedList Cycle that we create a slow point and a fast point: slow point moves to next node every time, while fast point moves to point next node of next node every time. When the fast point hits the end, slow point stops at the middle of the linked list. Then we apply merge sort starting at slow.next. After that, we want to apply merge sort again in the first half linkedlist, from head to slow. So we need to set slow.next to None.