1
class Solution {
2
  public ListNode partition(ListNode head, int x) {
3
    ListNode left = new ListNode(0);
4
    ListNode right = new ListNode(0);
5

6
    ListNode leftTail = left;
7
    ListNode rightTail = right;
8

9
    while (head != null) {
10
      if (head.val < x) {
11
        leftTail.next = head;
12
        leftTail = leftTail.next;
13
      } else {
14
        rightTail.next = head;
15
        rightTail = rightTail.next;
16
      }
17
      head = head.next;
18
    }
19

20
    leftTail.next = right.next;
21
    rightTail.next = null;
22

23
    return left.next;
24
  }
25
}