CTCI 2.4

Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

CTCI 2.4.java

public static void partitionList(Node root, int x){
    Node bigger = null;
    Node smaller = null;
    
    while(root != null){
        if(root.value >= x){
            if(bigger == null) bigger = root;
            else{
                bigger.next = root;
                bigger = root;
            }
        }
        else{
            if(smaller == null) smaller = root;
            else{
                root.next = smaller;
                smaller = root;
            }
        }
    }
    
    if(bigger == null || smaller == null) return (bigger != null)? bigger : smaller;
    else{
        bigger.next = smaller;
        return bigger;
    }
    
}