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)))
Such an amazingly simple solution. I was trying to think of implementing a quick-sort in a linked-list.
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?
self.merge(*map(self.sortList, (head, slow)))
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.