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.
*/
/**
* 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) {
ListNode root = new ListNode(0);
ListNode pivot = new ListNode(x);
ListNode root_next = root, pivot_next = pivot;
ListNode cur_node = head;
while(cur_node != null){
ListNode next = cur_node.next;
if(cur_node.val >= x){
pivot_next.next = cur_node;
pivot_next = cur_node;
pivot_next.next = null;
}else{
root_next.next = cur_node;
root_next = cur_node;
}
cur_node = next;
}
root_next.next = pivot.next;
return root.next;
}
public ListNode partitionJiuZhang(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 = head;
} else {
right.next = head;
right = head;
}
head = head.next;
}
right.next = null;
left.next = rightDummy.next;
return leftDummy.next;
}
}