Mergesort without fast and slow pointers


  • 0
    H
    class Solution:
        # @param {ListNode} head
        # @return {ListNode}
        def sortList(self, head):
            length=0
            pre=head
            self.head=head
            while pre:
                length+=1
                pre=pre.next
            return self.sort(length)
    
        def sort(self,n):
            if n==0:
                return None
            elif n==1:
                x=self.head
                self.head=self.head.next
                x.next=None
                return x
            else:
                if n/2+n/2<n:
                    
                    left=self.sort(n/2+1)
                    right=self.sort(n/2)
                else:
                    left=self.sort(n/2)
                    right=self.sort(n/2)
                return self.merge(left,right)
        def merge(self,node1,node2):
            pre=ListNode('*')
            head=pre
            while node1 and node2:
                if node1.val<node2.val:
                    pre.next=node1
                    node1=node1.next
                    pre=pre.next
                    pre.next=None
                else:
                    pre.next=node2
                    node2=node2.next
                    pre=pre.next
                    pre.next=None 
            if node1:
                pre.next=node1
            if node2:
                pre.next=node2
            return head.next
    

    got the idea from convert linked list to BST


  • 0

    With such long solutions it a little summary/explanation would be good. I came here because of the interesting title, but don't want to study that code just to find out the main idea.


Log in to reply
 

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