1 public class Solution {
2 public ListNode partition(ListNode head, int x) {
3 // IMPORTANT: Please reset any member data you declared, as
4 // the same Solution instance will be reused for each test case.
5 ListNode fakeLeftHead = new ListNode(0);
6 ListNode fakeRightHead = new ListNode(0);
7 ListNode leftRunner = fakeLeftHead;
8 ListNode rightRunner = fakeRightHead;
9
10 ListNode runner = head;
11 while(head != null){
12 ListNode next = head.next;
13 if(head.val < x){
14 leftRunner.next = head;
15 leftRunner = leftRunner.next;
16 head.next = null;
17 }
18 else{
19 rightRunner.next = head;
20 rightRunner = rightRunner.next;
21 head.next = null;
22 }
23 head = next;
24 }
25 leftRunner.next = fakeRightHead.next;
26 return fakeLeftHead.next;
27 }
28 }
