Question:

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.

Thinking:

We should preserve the original relative order of the nodes. So we need two points, one is for recording where to insert the less value node, and the other is for searching the less value node.

Solution1:

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null)
            return null;
        ListNode prehead = new ListNode(0);
        prehead.next = head;
        ListNode s = prehead;
        ListNode l = prehead;
        while(s != null && l != null){
            while(s.next != null){
                if (s.next.val >= x)
                    break;
                s = s.next;
            }
            l = s.next;
            if (l == null)
                break;
            while(l.next != null){
                if (l.next.val < x)
                    break;
                l = l.next;
            }
            if (l.next == null)
                break;
            ListNode tmp = l.next;
            l.next = l.next.next;
            tmp.next = s.next;
            s.next = tmp;
        }

        return prehead.next;
    }

}

And there is another solution, which uses two lists. One is for recording less value node, and the other is for recording greater value node. And connect them:

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

        ListNode small = new ListNode(-1);
        ListNode newsmallhead = small;
        ListNode big = new ListNode(-1);
        ListNode newbighead = big;

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

        small.next = newbighead.next;

        return newsmallhead.next;
}