Java Accepted: 3 ways quick sort with Circular linked list


  • 0
    W
    /**
     * Sort list
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
    	if (head == null) {
    		return null;
    	}
    	ListNode p = sort(head);
    	ListNode h = p.next;
    	p.next = null;
    	return h;
    }
    
    /**
     * 3 way quick sort with Circular linked list
     * @param head
     * @return
     */
    public ListNode sort(ListNode head) {
    	if (head == null) {
    		return null;
    	}
    	if (head.next == null) {
    		head.next = head;
    		return head;
    	}
    	ListNode smallHead = new ListNode(0);
    	ListNode midleHead = new ListNode(0);
    	ListNode largeHead = new ListNode(0);
    	ListNode smallTail = smallHead;
    	ListNode midleTail = midleHead;
    	ListNode largeTail = largeHead;
    
    	final int base = head.val;
    	while (head != null) {
    		if (head.val < base) {
    			smallTail.next = head;
    			smallTail = smallTail.next;
    		} else if (head.val > base) {
    			largeTail.next = head;
    			largeTail = largeTail.next;
    		} else{
    			midleTail.next = head;
    			midleTail = midleTail.next;
    		}
    		head = head.next;
    	}
    	smallTail.next = null;
    	largeTail.next = null;
    	midleTail.next = null;
    	
    	midleHead = midleHead.next;
    	largeHead = sort(largeHead.next);
    	smallHead = sort(smallHead.next);
    	
    	if (largeHead == null) {
    		largeHead = midleHead;
    		largeTail = midleTail;
    	}else{
    		largeTail = largeHead;
    		largeHead = largeHead.next;
    	}
    	
    	if (smallHead == null) {
    		smallHead = midleHead;
    		smallTail = midleTail;
    	}else{
    		smallTail = smallHead;
    		smallHead = smallHead.next;
    	}
    	
    	smallTail.next = midleHead;
    	midleTail.next = largeHead;
    	largeTail.next = smallHead;
    	return largeTail;
    }

  • 0
    T

    Is the space usage constant? As the function create three nodes and is invoked recursively, is the space usage constant?


  • 0
    W

    As you mentions, the space usage is not constant, because the function create nodes and invoked recursively.
    But these 3 lines :
    midleHead = midleHead.next;
    largeHead = sort(largeHead.next);
    smallHead = sort(smallHead.next);
    shows that the nodes created is not necessary, just for convenient in traversal.


Log in to reply
 

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