Easy recursive solution (beat 92%)


  • 0
    K

    The idea is to categorise nodes into 3 piles on each recursion: the values equal to, smaller than, and larger than the head one. Then sort the small and large piles, and finally connect them together with the equal one accordingly.

    def sortList(self, head):
            
            if head == None or head.next == None:
                return head
            
            pa=head
            pE=head
            pL=None
            pS=None
            while pa != None:            
                if pa.val == head.val:
                    pE,pE.next=pa,pE      
                elif pa.val > head.val:
                    pL,pL.next=,pa,pL             
                else:
                    pS,pS.next=pa,pS 
                pa=pa.next
    
            pL=self.sortList(pL)
            pS=self.sortList(pS)
            
            head.next=pL
    
            if pS:
                pa=pS
                while pa.next:
                    pa=pa.next
                pa.next=pE
                
            return pS or pE
    
    

Log in to reply
 

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