#CC150 #CC150-chap2 2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

PartitionLinkedList.java

package chap2;

/**
 * 2.4 Write code to partition a linked list around a value x, such that all
 * nodes less than x come before all nodes greater than or equal to x.
 * 
 * 
 * 
 * @author xl16
 * 
 */
public class PartitionLinkedList {

	/**
	 * Go through the list, if we see a node whose value is smaller than x,
	 * delete it and then insert it to the head of the list
	 * 
	 * Time O(n), Space O(1) if we are allowed to mutate the original list
	 * 
	 * @param head
	 * @param x
	 * @return
	 */
	public static Node partitionByInsertingToHead(Node head, int x) {
		// If there is only one node there is no point in doing partition
		if (head == null || head.next == null) {
			return head;
		}
		Node prev = head;
		Node current = head.next;
		Node next = null;
		Node newHead = head;

		while (current != null) {
			next = current.next;
			if (current.data < x) {
				// Delete it
				prev.next = current.next;
				// Insert it to the head
				current.next = newHead;
				// Set the new head
				newHead = current;
			} else {
				// move the previous pointer
				prev = current;
			}
			current = next;
		}
		return newHead;
	}

	/**
	 * Solution 1 in the book, use two lists, one to store the nodes whose value
	 * are lower then x, one to store the others. Finally, merge them together. Solution 2 is very similer, that adds to the head. See the book.
	 * 
	 * Time O(n), Space O(1)  if we are allowed to mutate the original list
	 * 
	 * @param head
	 * @param x
	 * @return
	 */
	public static Node partitionListWithTwoLists(Node head, int x) {
		// If there is only one node there is no point in doing partition
		if (head == null || head.next == null) {
			return head;
		}
		Node lower = null;
		Node lowerEnd = null;

		Node equalOrHigher = null;
		Node equalOrHigherEnd = null;
		Node nextNode = null;
		while (head != null) {
			nextNode = head.next;
			head.next = null;
			if (head.data < x) {
				// Add the node to the lower list
				if (lower == null) { // Initialize
					lower = head;
					lowerEnd = lower;
				} else {
					lowerEnd.next = head;
					lowerEnd = head;
				}
			} else {
				if (equalOrHigher == null) { // Initialize
					equalOrHigher = head;
					equalOrHigherEnd = equalOrHigher;
				} else {
					equalOrHigherEnd.next = head;
					equalOrHigherEnd = head;
				}
			}
			head = nextNode;
		}
		// Merge the two lists together
		if (lower == null) {
			return equalOrHigher;
		}
		lowerEnd.next = equalOrHigher;
		return lower;
	}

	/**
	 * Implementation of a simple LinkedList
	 * 
	 * @author xl16
	 * 
	 */
	static class Node {
		Node next = null;
		int data;

		public Node(int d) {
			data = d;
		}

		public void appendToTail(int d) {
			Node end = new Node(d);
			Node n = this;
			while (n.next != null) {
				n = n.next;
			}
			n.next = end;
		}

		public String toString() {
			Node n = this;
			String str = "";
			while (n.next != null) {
				str += String.valueOf(n.data) + "->";
				n = n.next;
			}
			// The last node
			str += String.valueOf(n.data) + "->null";
			return str;
		}
	}

	public static void main(String args[]) {
		PartitionLinkedList.Node n = new Node(3);
		n.appendToTail(1);
		// n.appendToTail(0);
		// n.appendToTail(4);

		int x = 2;

		System.out.println("Original                 : " + n.toString());
		// Node result = partitionListWithTwoListsAnotherWayOfWriting(n, x);
		System.out.println("Result                   : "
				+ partitionByInsertingToHead(n, x).toString());

	}
}