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

7
    ListNode *leftTail = left;
8
    ListNode *rightTail = right;
9

10
    while (head != NULL) {
11
      if (head->val < x) {
12
        leftTail->next = head;
13
        leftTail = leftTail->next;
14
      } else {
15
        rightTail->next = head;
16
        rightTail = rightTail->next;
17
      }
18
      head = head->next;
19
    }
20

21
    leftTail->next = right->next;
22
    rightTail->next = NULL;
23

24
    return left->next;
25
  }
26
};