[python]Sort List LTE


  • 0
    D
    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if None == head or None == head.next:
            return head
        pivot = head
        node = head.next
        less = None
        greater = None
    
        while None != node:
            tmp = node.next
            if pivot.val > node.val:
                node.next = less
                less = node
            else:
                node.next = greater
                greater = node
            node = tmp
     
        less = self.sortList(less)
        if less != None:
            node = less
            while node.next != None:
                node = node.next
            node.next = pivot
        else:
            less = pivot
    
        greater = self.sortList(greater)
        pivot.next = greater
    
        return less

  • 0
    D

    i got it,if there are many numbers which are the same in the list, the code will waster too much time to handle it .


  • 0
    D
    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if None == head or None == head.next:
            return head
        pivot   = head
        node    = head.next
        less_list    = None
        greater_list = None
        equal_list   = pivot
    
        while None != node:
            tmp = node.next
            if pivot.val > node.val:
                node.next = less_list
                less_list = node
            elif pivot.val < node.val:
                node.next = greater_list
                greater_list = node
            else:
                equal_list.next = node
                equal_list = node
            node = tmp
        #greater_list指向等于pivot的链表
        equal_list.next = None
        #less_list指向小于pivot的链表
        less_list = self.sortList(less_list)
        #greater_list指向大于pivot的链表
        greater_list = self.sortList(greater_list)
        less_list = self.connect(less_list, pivot, greater_list)
    
        return less_list
    
    def connect(self, less_list, pivot, greater_list):
        node = pivot
        while True:
            if node.next == None:
                node.next = greater_list
                break
            node = node.next
    
        node = less_list
        if less_list == None:
            less_list = pivot
        else:
            while node.next != None:
                node = node.next
            node.next = pivot
        return less_list

  • 0
    C

    on the last part of 'connect', I think the while loop will result in a O(n^2) in the worst case. Am I right?


  • 0
    D

    yes,quick sort will be O(n^2) in the worst case which less than pivot was empty and greater than pivot was full.


  • 0
    C

    in your code, it the 'less than pivot' list that causes the worst case.


  • 0
    D

    absolutely yes, i can choose pivot by ramdon to eliminate this case.


  • 0
    C

    i don't think randomize the pivot will help the last while loop in 'connect'.
    Btw, you can use 'equal_list.next = great_list' to replace the first while loop


  • 0
    D

    you mean:
    def connect(self, less_list, pivot, equal_list, greater_list):
    equal_list.next = greater_list
    node = less_list
    if less_list == None:
    less_list = pivot
    else:
    while node.next != None:
    node = node.next
    node.next = pivot
    return less_list

    right?


  • 0
    C

    that is what I meant


  • 0
    D

    thank you!you are right.


Log in to reply
 

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