From seeing several most voted solutions, most of them are to store two queues and link them finally. However, I cam up with another solution, the idea was form the insertion sort.

EX. 1->4->3->2->5->2 X= 3

step 1: find the first node that bigger than the pivot (4 in this example)

step 2: do a while loop from head, whenever finding a node that is smaller than pivot, we will insert it before the firstBig node

below is my java code, but it always shows runtime error due to a nullPointerException. I cannot find the bug, is there anybody could help me?

Please don't give me a downvote, I have tried to solve this problem for more than 2 hours and the main reason I posted it is to share my thinking. Thanks.

```
public ListNode partition(ListNode head, int x) {
//same way with insertion sort
if(head == null || head.next == null) return head;
ListNode cur = head;
ListNode next = head.next;//next means the next first smaller node after the cur
ListNode prevNext = head;// prev node of the next node
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;//prev means the last smaller node before the cur
ListNode firstBig;
//first find the first node that bigger or equal than pivot node
while(cur != null && cur.val < x) {
cur = cur.next;
}
if(cur == null) return dummy.next;
else {
firstBig = cur;
cur = head;
}
while(cur != null) {
if(cur.val >= x) {
//find the fisrt smaller node after the cur
while(next != null && next.val >= x ) {
prevNext = next;
next = next.next;
}
if(next != null) {
//next node found
prevNext.next = next.next;
prev.next = next;
next.next = firstBig;
} else {
break;//all the following node are larger than pivot
}
}
prev = prev.next;
cur = cur.next;
next = cur.next;
}
return dummy.next;
}
```