Clean concise mergesort Python solution


  • 1
    T
    class Solution(object):
        def sortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head:
                return None
            if not head.next:
                return head
            pre, slow, fast = None, head, head
            while fast and fast.next:
                pre, slow, fast = slow, slow.next, fast.next.next
            pre.next = None
            left, right = self.sortList(head), self.sortList(slow)
            pre_head = cur = ListNode(None)
            while left and right:
                if left.val < right.val:
                    cur.next, left.next, left = left, None, left.next
                else:
                    cur.next, right.next, right = right, None, right.next
                cur = cur.next
            if left or right:
                cur.next = left or right
            return pre_head.next
    

Log in to reply
 

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