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.

The idea is to use two node, keep appending node smaller than the target to smaller node, keep appending node larger or equal to the target to larger node, then set last larger node point to null and set the last smaller node point to the first larger node.

public ListNode partition(ListNode head, int x) {
        if (head==null||head.next==null) {
            return head;
        }

        ListNode larger = new ListNode(0);
        ListNode newLargerHead = larger;
        ListNode smaller = new ListNode(0);
        ListNode newSmallerHead = smaller;


        while (head!=null) {
            if (head.val<x) {
                smaller.next = head;
                smaller = smaller.next;
            } else {
                larger.next = head;
                larger = larger.next;
            }
            head = head.next;
        }

        larger.next = null;

        //point the last smaller element to the first larger one
        smaller.next = newLargerHead.next;

        return newSmallerHead.next;
    }