1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode * partition(ListNode *head, int x) {
12         ListNode dummy_left(-1), dummy_right(-1);
13         ListNode *pl = &dummy_left, *pr = &dummy_right;
14         for (ListNode * p = head; p != nullptr; p = p->next) {
15             if (p->val < x) {
16                 pl->next = p;
17                 pl = pl->next;
18             } else {
19                 pr->next = p;
20                 pr = pr->next;
21             }
22         }
23         pl->next = dummy_right.next;
24         pr->next = nullptr;
25         return dummy_left.next;
26     }
27 };