Python O(1) space and O(nlogn) time solution(but slow, please advice)


  • 0
    D

    The difficulty of this one is O(1) space, my idea is to apply quick sort algorithm as follows, and code is in the answer part.

    1 Given a list, chose the first element to be the pivotal value.

    2 Scan through the list, take out every element equal to or smaller than pivotal value to form a second list called "smaller"

    3 (important, otherwise TLE) check the smaller list, if at the end there are several nodes that has the same value as standard value, shrink the smaller list to exclude those nodes. By the end of this step, you got 3 part, smaller list, pivotal, bigger list.

    4 Apply the smaller list and bigger list to the function recursively.

    5 Join these three parts together to form a sorted list.


  • 0
    D
     class Solution(object):
                def sortList(self, head):
                    """
                    :type head: ListNode
                    :rtype: ListNode
                    """
                    def mysort(head):
                        """
                        :type head: ListNode
                        :rtype: (ListNode head, ListNode tail)
                        """
                        if not head: # Len = 0
                            return None, None
                        if not head.next: # len = 1
                            return (head, head) #  Length 0 or 1
                        # Step 1, use the first node to devide the whole list into 3 parts. Smaller, mid, bigger
                        mid = head
                        s_head = None
                        s_tail = None
                        i = mid
                        while i and i.next:
                            if i.next.val <= mid.val:
                                # Take a copy of this node to the smaller list.
                                if not s_head: #  Find the first smaller node
                                    s_head = copy(i.next)
                                    s_tail = s_head
                                else:
                                    s_tail.next = copy(i.next)
                                    s_tail = s_tail.next
                                #  Then delete the smaller node from main list                    
                                i.next = i.next.next
                            else:
                                i = i.next
                        if s_tail:
                            s_tail.next = mid
                        
                        #  Step 2: Get the bigger part sorted.
                        new_head_bigger, new_end_bigger = mysort(mid.next) 
                        mid.next = new_head_bigger
                        #  Step 3: Get the smaller part sorted
                        last_diff_node = None
                        n = s_head
                        while n and n is not mid:
                            if n.val < mid.val:
                                last_diff_node = n
                            n = n.next
                        if last_diff_node:
                            mid_start = last_diff_node.next
                            last_diff_node.next = None
                            new_head_smaller, new_end_smaller = mysort(s_head)
                        else:
                            new_head_smaller, new_end_smaller = s_head, s_tail
                            mid_start = mid
                        # Step 4, join.
                        #  There is only bigger list
                        if not new_head_smaller and new_head_bigger:
                            return mid_start, new_end_bigger
            
                        # There is only a smaller list
                        if not new_head_bigger and new_head_smaller:
                            new_end_smaller.next = mid_start
                            return new_head_smaller, mid
                        # There are both bigger and smaller lists
                        if new_head_smaller and new_head_bigger:
                            new_end_smaller.next = mid_start
                            mid.next = new_head_bigger # Concatenate two list and return
                            return new_head_smaller, new_end_bigger
                    return mysort(head)[0]

Log in to reply
 

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