Merge sort using fast and slow pointer - Python solution


  • 0
    V
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param {ListNode} head
        # @return {ListNode}
        def sortList(self, head):
            if not head or not head.next:
                return head
            
            slow = head
            fast = head.next
            
            while fast and fast.next:
                fast = fast.next.next
                slow = slow.next
            
            right = self.sortList(slow.next)
            slow.next = None
            left = self.sortList(head)
            
            return self.merge(left, right)
        
        def merge(self, l1, l2):
            dummy = cur = ListNode(0)
            
            while l1 and l2:
                if l1.val <= l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            
            cur.next = l1 or l2
            return dummy.next

Log in to reply
 

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