Solution not using two lists


  • 0
    Q

    Not using two lists to storing separately the smaller chain and the bigger chain and then join them, but directly move part by part the smaller partition to the their required places.

    If values of all nodes are smaller or bigger then the given value, then return without modification.
    Else using several pointers to track the partitions (nodes chain with value smaller than the given one) and move them to their required places. Have to track the position to insert, the node before and after each partition, and the next position to continue.

    public ListNode partition(ListNode head, int x) {
            ListNode header = new ListNode(0);
    		header.next = head;
    		ListNode previous = header;
    		ListNode current = head;
    		ListNode partitionPrevious = current;
    		ListNode partitionLast = current;
    		
    		while (current != null && current.val < x) {
    			previous = current;
    			current = current.next;
    		}
    		// all elements < x
    		if (current == null) {
    			return head;
    		}
    		
    		while (current != null) {
    			// find the node previous to the current partition
    			while (current != null && current.val >= x) {
    				partitionPrevious = current;
    				current = current.next;
    			}
    			
    			if (current == null) {
    				break;
    			}
    			
    			// find the end partition node
    			while (current != null && current.val < x) {
    				partitionLast = current;
    				current = current.next;
    			}
    			
    			ListNode temp = previous.next;
    			previous.next = partitionPrevious.next;
    			partitionPrevious.next = current;
    			partitionLast.next = temp;
    			
    			previous = partitionLast;
    		}
    
    		return header.next;
        }

Log in to reply
 

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