Partition linkedlist such that all nodes less than x come before nodes greater than or equal to x.

ListNode.java

package com.interviewbytes.linkedlists;

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

Partition.java

package com.interviewbytes.linkedlists;

public class Partition {

    public ListNode partition(ListNode head, int x) {

        ListNode lesserSentinel = new ListNode(0);
        ListNode greaterSentinel = new ListNode(0);

        ListNode currentLesser = lesserSentinel;
        ListNode currentGreater = greaterSentinel;

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

        currentLesser.next = greaterSentinel.next;
        currentGreater.next = null;

        return lesserSentinel.next;
    }
}