CC_2_4

ListPartition.java

// Cracking the Coding Interview
// 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.

class Node {
	public Node next;
	public int val;
	Node(int _v) {
		val = _v;
		next = null;
	}
}

class ListPartition {
	public static Node partitionList(Node head, int v) {
		if (head == null || head.next == null) return head;
		Node less = new Node(0);
		Node lessHead = less;
		Node greater = new Node(0);
		Node greaterHead = greater;
		Node cur = head;
		while (cur != null) {
			if (cur.val < v) {
				less.next = cur;
				less = less.next;
				cur = cur.next;
				less.next = null;
			} else {
				greater.next = cur;
				greater = greater.next;
				cur = cur.next;
				greater.next = null;
			}
			
		}
		if (lessHead.next == null) {
			return greaterHead.next;
		} else {
			less.next = greaterHead.next;
			return lessHead.next;
		}
	}

	public static void main(String[] args) {
		Node test1 = arrayToLinkedList(new int[]{1});
		Node test2 = arrayToLinkedList(new int[]{1, 2});
		Node test3 = arrayToLinkedList(new int[]{1, 2});
		Node test4 = arrayToLinkedList(new int[]{3, 2, 1, 4});
		Node test5 = arrayToLinkedList(new int[]{3, 2, 1, 4});
		Node test6 = arrayToLinkedList(new int[]{3, 2, 2, 4, 1});

		assert compareLinkedList(partitionList(test1, 2), arrayToLinkedList(new int[]{1}));
		assert compareLinkedList(partitionList(test2, 3), arrayToLinkedList(new int[]{1, 2}));
		assert compareLinkedList(partitionList(test3, 0), arrayToLinkedList(new int[]{1, 2}));
		assert compareLinkedList(partitionList(test4, 2), arrayToLinkedList(new int[]{1, 3, 2, 4}));
		assert compareLinkedList(partitionList(test5, 4), arrayToLinkedList(new int[]{3, 2, 1, 4}));
		assert compareLinkedList(partitionList(test6, 2), arrayToLinkedList(new int[]{1, 3, 2, 2, 4}));

		System.out.println("Test Passed");
	}

	private static boolean compareLinkedList(Node a, Node b) {
		Node p1 = a;
		Node p2 = b;
		while (p1 != null && p2 != null) {
			if (p1.val != p2.val) {
				return false;
			} else {
				p1 = p1.next;
				p2 = p2.next;
			}
		}

		return p1 == null && p2 == null;
	}

	private static Node arrayToLinkedList(int[] arr) {
		if (arr == null || arr.length < 1) return null;
		Node fakeHead = new Node(0);
		Node cur = fakeHead;
		for(int i = 0; i < arr.length; i++) {
			cur.next = new Node(arr[i]);
			cur = cur.next;
		}
		return fakeHead.next;
	}
}

1. Good job!