Partition List
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.
SOLUTION 1:
注意使用Dummynode来记录各个链条的头节点的前一个节点。这样我们可以轻松找回头节点。
1. Go Through the link, find the nodes which are bigger than N, create a new link.
2. After 1 done, just link the two links.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null) {
return null;
} ListNode dummy = new ListNode(0);
dummy.next = head; ListNode pre = dummy;
ListNode cur = head; // Record the big list.
ListNode bigDummy = new ListNode(0);
ListNode bigTail = bigDummy; while (cur != null) {
if (cur.val >= x) {
// Unlink the cur;
pre.next = cur.next; // Add the cur to the tail of the new link.
bigTail.next = cur;
cur.next = null; // Refresh the bigTail.
bigTail = cur; // 移除了一个元素的时候，pre不需要修改，因为cur已经移动到下一个位置了。
} else {
pre = pre.next;
} cur = pre.next;
} // Link the Big linklist to the smaller one.
pre.next = bigDummy.next; return dummy.next;
}
}
CODE:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/list/Partition.java