Python merge sort solution using fast & slow pointers


  • 0
    S
    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:
                    cur.next = lower
                    lower = lower.next
                    cur = cur.next
                else:
                    cur.next = upper
                    upper = upper.next
                    cur = cur.next
            
            while lower:
                cur.next = lower
                cur = cur.next
                lower = lower.next
                
            while upper:
                cur.next = upper
                cur = cur.next
                upper = upper.next
                
            # disconnect last.next
            # At this point, cur is the last item
            cur.next = None
            
            return handle.next
        
        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 = fast.next
                if not fast: break
                
                prev = slow
                slow = slow.next
                fast = fast.next
            
            # Need to make sure to disconnect the reference
            
            if prev:
                prev.next = 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.