partition_list.java

/**
 * 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;
    }
}