The following is my accepted solution:

```
public class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null) {
return null;
}
ListNode leftEnd = null; //the end of the first half (nodes which have the smaller value than x)
ListNode previous = null;
if (head.val < x) {
leftEnd = head;
}
previous = head;
ListNode node = head.next;
while (node != null) {
if (node.val < x) {
if (leftEnd == null || leftEnd.next != node) { //need to insert into the first half
previous.next = node.next;
if(leftEnd != null) { //insert the node
node.next = leftEnd.next;
leftEnd.next = node;
} else if (leftEnd == null){ //the first one which is less than x, let it be the new head
node.next = head;
head = node;
}
leftEnd = node;
node = previous.next;
continue;
} else { //not need to insert, just move the leftEnd
leftEnd = node;
}
}
//node.val > x
previous = node;
node = node.next;
}
return head;
}
}
```

And I know there is another way to solve this question. We can construct two sub lists, one is for the nodes with smaller value and another is for larger value. And then concatenate such two lists to get the final list.

So which one is better? Do we need any extra space to use two sub lists?