Share my Python solution (Merge Sort)


  • 0
    M
    class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return head 
        
        middle = head
        fast = head
    
        # Find middle node
        while fast.next and fast.next.next:
            fast = fast.next.next
            middle = middle.next
        
        sec = middle.next
        middle.next = None
    
        # If middle == head, the list length is 2
        if head != middle:
            head = self.sortList(head)
            sec = self.sortList(sec)
        
        # Merge head and sec linked list
        tmp_node = ListNode(-1)
        res = tmp_node
        
        while head and sec:
            if head.val > sec.val:
                tmp_node.next = sec
                sec = sec.next
            else:
                tmp_node.next = head
                head = head.next
            
            tmp_node = tmp_node.next
    
        while head:
            tmp_node.next = head
            head = head.next
            tmp_node = tmp_node.next
        
        while sec:
            tmp_node.next = sec
            sec = sec.next
            tmp_node = tmp_node.next
        
        head = res.next
        return head

Log in to reply
 

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