/**
* 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 || head.next == null) return head;
ListNode l,r; // l points to the LESS part end, r points to the GREATER part end
/**
x = 3
a:
1 2 2 3 4 1
L R
b:
(null) 4 3 2 1 1
L R
*/
ListNode newHead = head;
// init the two points
if(head.val < x){
l = head;
while(l.next != null && l.next.val < x){
l = l.next;
}
r = l.next;
if(r == null) return head; // all nodes are less than x, return head
while(r.next != null && r.next.val >= x)
r = r.next;
}else{
l = null;
r = head;
while(r.next != null && r.next.val >= x) r = r.next;
if(r.next == null) return head; // all nodes are greater than or equal to x, return head
}
// move the r pointer
while(r.next != null){
// find the first node which belongs to left part, or reach the end
while(r.next != null && r.next.val >= x) r = r.next;
ListNode n = r.next;
if(n == null) return newHead; // reach the end, return
r.next = n.next;
if(l != null){ // first circumstances
n.next = l.next; // move node n to the end of the first part, then update pointer l
l.next = n;
l = n;
}else{ // second circumstances, empty left part
n.next = head;
l = newHead = n;
}
}
return newHead;
}
}