Leetcode: Partition List (Java)

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.

The key is to use fake header, one includes all smaller nodes, another includes all equal or greater nodes.
You should preserve the original relative order of the nodes in each of the two partitions.
public ListNode partition(ListNode head, int x) {

if (head==null || head.next==null){

return head;

}

// leftSide 

ListNode preLeftHead=new ListNode (-1);

ListNode leftEnd=preLeftHead;

// rightSide

ListNode preRightHead=new ListNode(-1);

ListNode rightEnd=preRightHead;

ListNode run=head;

while (run!=null){

ListNode temp=run.next;

if (run.val<x){

leftEnd.next=run;

leftEnd=leftEnd.next;

}

else{

rightEnd.next=run;

rightEnd=rightEnd.next;

}

run.next=null;

run=temp;

}

// connect left and right

leftEnd.next=preRightHead.next;       

return preLeftHead.next;

}

Another solution from http://www.darrensunny.me/leetcode-partition-list/

public ListNode partition(ListNode head, int x) {

        if (head == null)

            return null;

 

        // Use a sentinel to avoid boundary check

        ListNode sentinel = new ListNode(0);

        sentinel.next = head;

 

        // Find the node whose next is the first one not smaller than x

        ListNode preFirstLarger = sentinel;

        while (preFirstLarger.next != null && preFirstLarger.next.val < x)

            preFirstLarger = preFirstLarger.next;

        if (preFirstLarger.next == null)

            return head;

 

        // Each time we meet a node smaller than x, we move it to before the first

        // one not smaller than x

        ListNode pre = preFirstLarger.next, current = pre.next;

        while (current != null) {

            if (current.val < x) {

                pre.next = current.next;

                current.next = preFirstLarger.next;

                preFirstLarger.next = current;

                preFirstLarger = preFirstLarger.next;

                current = pre.next;

            } else {

                pre = current;

                current = current.next;

            }

        }

 

        return sentinel.next;

    }

Read full article from My Leetcode: Partition List (Java)