Python merge sort solution using fast & slow pointers

  • 0
    class Solution:
        # @param {ListNode} head
        # @return {ListNode}
        def sortList(self, head):
            (lower, upper) = self.halve_list(head)
            # then there is only one thing in the list
            if lower == upper: return lower
            lower = self.sortList(lower)
            upper = self.sortList(upper)
            return self.merge_list(lower, upper)
        def merge_list(self, lower, upper):
            handle = ListNode(None)
            cur = handle
            while lower and upper:
                if lower.val < upper.val:
           = lower
                    lower =
                    cur =
           = upper
                    upper =
                    cur =
            while lower:
       = lower
                cur =
                lower =
            while upper:
       = upper
                cur =
                upper =
            # disconnect
            # At this point, cur is the last item
   = None
        def halve_list(self, head):
            fast = slow = head
            # advance fast two at a time
            # advance slow one at a time
            # when fast hits the end; slow is mid point
            prev = None
            while fast:
                fast =
                if not fast: break
                prev = slow
                slow =
                fast =
            # Need to make sure to disconnect the reference
            if prev:
       = None
            # slow is the start of upper half
            # head is the start
            return (head, slow)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.