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.