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.

CC150-2.4.java

public class Main {

	/**
	 * 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.
	 * 
	 * @Runtime & spaces
	 * runtime: O(n)
	 * space:   O(1)
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main so = new Main();
		ListNode a = new ListNode(5);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(3);
		ListNode d = new ListNode(7);
		ListNode e = new ListNode(1);
		ListNode f = new ListNode(2);
		ListNode g = new ListNode(6);
		a.next = b;
		b.next = c;
		c.next = d;
		d.next = e;
		e.next = f;
		f.next = g;
		ListNode p = so.partition(a, 2);
		while (p != null) {

			System.out.println(p.val);
			p = p.next;
		}
	}

	public ListNode partition(ListNode p, int x) {
		if (p == null || p.next == null)
			return p;
		ListNode beforeStart = new ListNode(0);
		ListNode beforeEnd = beforeStart;
		ListNode afterStart = new ListNode(0);
		ListNode afterEnd = afterStart;

		while (p != null) {
			// 把一个node独立出来了
			ListNode next = p.next;
			p.next = null;
			if (p.val < x) {
				beforeEnd.next = p;
				beforeEnd = p;
			} else {
				afterEnd.next = p;
				afterEnd = p;
			}
			p = next;
		}
		beforeEnd.next = afterStart.next;
		return beforeStart.next;
	}
}