Clean python code


  • 35
    class Solution(object):
        def merge(self, h1, h2):
            dummy = tail = ListNode(None)
            while h1 and h2:
                if h1.val < h2.val:
                    tail.next, tail, h1 = h1, h1, h1.next
                else:
                    tail.next, tail, h2 = h2, h2, h2.next
        
            tail.next = h1 or h2
            return dummy.next
        
        def sortList(self, head):
            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)))

  • 0
    X

    Really clean and helpful, thanks.


  • 0
    G

    Such an amazingly simple solution. I was trying to think of implementing a quick-sort in a linked-list.


  • 11
    J

    Recursion is not constant space.


  • 1
    A

    What's the meaning of the * in the last line?


  • 0
    Z

    What is the advantage of the pre node?


  • 1
    P

    @haoli

    f(*[1,2,...]) = f(1,2,...)
    

  • 0
    W

    @alphashaw said in Clean python code:

    What's the meaning of the * in the last line?

    not sure about the * either.
    what does the 'map' do in the last line?
    Can anyone explain the last line in more details?
    Thanks!


  • 5
    D

    @www
    self.merge(*map(self.sortList, (head, slow)))
    equals
    self.merge(self.sortList(head),self.sortList(slow))


  • 0
    W

    @doraemon1293
    This explains.
    Thank you!


  • 1

    @zeusidkz
    Need to break current linked list into two equal lengths linked lists when we run a merge. That's what pre is used for. Maybe someone would ask why can't we just make slow.next = None after the while loop. But we need slow to be the start point of the later half linked list.


  • 0
    B

    Can someone explain to me this line?
    tail.next, tail, h1 = h1, h1, h1.next.

    It seems that the second tail = h1 already overwrite what the first assignment did. Therefore no matter what the first assignment did, tail would eventually become h1. Is this correct?


Log in to reply
 

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