Short and clean python quick sort solution.


  • 2
    M

    The ticky is dividing the list into three part in every scan loop. Left part is less than pivot, middle part is equals to pivot, and right part is greater than pivot.

    # requirement: hat is not None
    def quick_sort(hat, tail):
        if hat.next is tail or hat.next.next is tail:
            return
    
        hat1, hat2, hat3 = hat, hat.next, ListNode(None)
        tail1, tail2, tail3 = hat1, hat2, hat3
        p, pivot = hat2.next, hat2.val
        while p is not tail:
            if p.val < pivot:
                tail1.next, tail1, p = p, p, p.next
            elif p.val == pivot:
                tail2.next, tail2, p = p, p, p.next
            else:
                tail3.next, tail3, p = p, p, p.next
    
        # Caution: DO NOT change the order of these three line codes below. 
        tail3.next = tail
        tail2.next = hat3.next
        tail1.next = hat2
    
        quick_sort(hat1, hat2)
        quick_sort(tail2, tail)
    
    
    class Solution:
        # @param {ListNode} head
        # @return {ListNode}
        def sortList(self, head):
            hat = ListNode(None)
            hat.next = head
            quick_sort(hat, None)
            return hat.next

  • 0
    J

    I have a question, is recursive solution considered `constant space complexity'? Cause the stack will use O(nlogn) space if it is called recursively.


  • 0
    M

    Hi, JinhongChen. You are right, this solution can not be considered "constant space complexity". Since it is recursive, the stack will use O(log(n)) space.
    By the way, could anyone find a constant space complexity and a O(n*log(n)) time complexity solution for this problem?


  • 0

    Use iterative method then. But I do favor writing recursive solution for quick-sort or merge-sort problems


  • 0
    M

    I think the iterative method can't be considered "constant space complexity" too. Because it uses a manual stack.


  • 0
    F

    Hi, MissMary. Mergesort solution would have constant space complexity since we don't need to use extra storage for "merge". I've implemented it as following:

    1. Start from the head of the list (let it be n1)
    2. Follow the pointers from n1 to find the next node with smaller value than the previous (let it be n2)
    3. Call merge with n1 and n2. Merge will proceed until we processed all elements from n1 to n2 and encountered the value smaller than the previous one in the sequence starting with n2. Return the node with that smaller value and use it as new n1. Remember the fact that you called merge.
    4. Repeat until you reach the end of the list.
    5. Check if you called merge during this run. If not, the array is sorted, otherwise - reset n1 to head and repeat.

    Step 5 might be optimized a bit to avoid an extra pass in some cases.


  • 0
    M

    Hi, freevoid. This is really a good idea. Thank you very much. Would you provide your AC code?


  • 0
    F

    Sure, here it is:

    class Solution(object):
        def sortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            return merge_sort(head)
            
    def merge_sort(head):
        node = head
        node_prev = None
        merges_in_pass = 0
        while True:
            node2_prev = node
            if node:
                node2 = node.next
            else:
                node2 = None
    
            while node2 and node2.val >= node2_prev.val:
                node2_prev = node2
                node2 = node2.next
    
            if node2 is not None:
                assert node2_prev is not None
                head, node, node_prev = merge(node, node2, node_prev, node2_prev, head)
                merges_in_pass += 1
            else:
                if merges_in_pass > 1 or (merges_in_pass == 1 and node is not None):
                    node = head
                    node_prev = None
                    merges_in_pass = 0
                else:
                    return head
    
    
    def merge(n1, n2, n1_prev, n2_prev, head):
        if n2 is None:
            return head, n2, n2_prev
    
        new_head = head
        while n1 != n2 and n2 is not None:
            if n1.val <= n2.val:
                n1_prev = n1
                n1 = n1.next
            else:
                next_n2 = n2.next
                n2_prev.next = next_n2
                if n1_prev is None:
                    new_head = n2
                else:
                    n1_prev.next = n2
                n2.next = n1
                n1_prev = n2
                
                if next_n2 and n2.val > next_n2.val:
                    n2 = next_n2
                    break
                else:
                    n2 = next_n2
    
        while n2 and n2.val >= n2_prev.val:
            n2_prev = n2
            n2 = n2.next
    
        return new_head, n2, n2_prev

Log in to reply
 

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