Partition List @LeetCode

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

	package leetcode.linkedlist;
	/**
	* Solution: Split list into two list, one's value < x, one's >= x. and the merge two List together.
	* All three methods are same, little difference in coding.
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class Partition {
	/**
	* Solution1: Dummy Node -- very ingenious method.
	* 1. Only need left, right as end pointer, start pointer use Dummy node.
	* 2. Don't forget right.next = null. becuase the last right node may not the last node in orginal list.
	*
	* 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
	* Why 1 2 2 4 3 5 but not 1 2 2 3 4 5. left < x, right >=x, and We must keep preserve original order.
	*/
	public ListNode partition(ListNode head, int x) {
	if (head == null) {
	return null;
	}
	ListNode leftDummy = new ListNode(0);
	ListNode rightDummy = new ListNode(0);
	ListNode left = leftDummy, right = rightDummy;
	while (head != null) {
	if (head.val < x) {
	left.next = head;
	left = left.next;
	} else {
	right.next = head;
	right = right.next;
	}
	head = head.next;
	}
	right.next = null; // important
	left.next = rightDummy.next;
	return leftDummy.next;
	}
	/**
	* Solution2: Split into two list and each with start pointer and then merge.
	* LeetCode Online judge says Answer wrong, because I insert every node in the head. the sequence is not ascending order.
	* But it really works.
	*/
	public ListNode partition2(ListNode head, int x) {
	if (head == null || head.next == null) {
	return head;
	}
	ListNode beforeStart = null;
	ListNode afterStart = null;
	while(head != null) {
	ListNode next = head.next;
	if (head.val < x) {
	head.next = beforeStart;
	beforeStart = head;
	} else {
	head.next = afterStart;
	afterStart = head;
	}
	head = next;
	}
	if (beforeStart == null) {
	return afterStart;
	}
	head = beforeStart;
	while(beforeStart.next != null) {
	beforeStart = beforeStart.next;
	}
	beforeStart.next = afterStart;
	return head;
	}
	/**
	* Solution3: same to Solution2, split into two list and each with start and end pointer. this one could AC on LeetCode.
	* Don't forget head.next = null!!! cut the list node!
	* Solution2 don't need to cut because it insert in the head.
	*/
	public ListNode partition3(ListNode head, int x) {
	ListNode beforeStart = null;
	ListNode beforeEnd = null;
	ListNode afterStart = null;
	ListNode afterEnd = null;
	while (head != null) {
	ListNode next = head.next;
	head.next = null;
	if (head.val < x) {
	if (beforeStart == null) {
	beforeStart = head;
	beforeEnd = head;
	} else {
	beforeEnd.next = head;
	beforeEnd = beforeEnd.next;
	}
	} else {
	if (afterStart == null) {
	afterStart = head;
	afterEnd = head;
	} else {
	afterEnd.next = head;
	afterEnd = afterEnd.next;
	}
	}
	head = next;
	}
	if (beforeStart == null) {
	return afterStart;
	}
	beforeEnd.next = afterStart;
	return beforeStart;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw Partition.java hosted with ❤ by GitHub