Python solution


  • 0
    Q

    Basically the same thing as this one: https://leetcode.com/problems/sort-list/discuss/46710/?page=1

    I rewrote the merge part to make it easier to understand because I saw some questions around it.

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def merge(self, h1, h2):
                dummy = tail = ListNode(None)
                while h1 and h2:
                    if h1.val < h2.val:
                        tail.next = h1
                        tail = tail.next
                        h1 = h1.next
                    else:
                        tail.next = h2
                        tail = tail.next
                        h2 = h2.next
    
                tail.next = h1 or h2
                return dummy.next
            
        def sortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head or 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
    
            return self.merge(*map(self.sortList, (head, slow)))
    

Log in to reply
 

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