CC2.4.java

    public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null)
            return head;
        ListNode lessHead, nolessHead, lessCur, nolessCur;
        lessHead = nolessHead = lessCur = nolessCur = null;
        ListNode cur, next;
        cur = head;
        while(cur != null) {
            next = cur.next;
            cur.next = null;        // cut off cur node from the list
            if(cur.val < x) {
                if(lessHead == null)
                    lessHead = cur;
                else
                    lessCur.next = cur;
                lessCur = cur;
            } else {
                if(nolessHead == null)
                    nolessHead = cur;
                else
                    nolessCur.next = cur;
                nolessCur = cur;
            }
            cur = next;
        }
        
        // connect two lists
        if(lessCur != null)
            lessCur.next = nolessHead;
        ListNode newHead;
        newHead = (lessHead == null) ? nolessHead : lessHead;
        return newHead;
    }