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         if (head == NULL || head->next == NULL) {
13             return head;
14         }  
15         // "P" holds the track of the linked list
16         // "pre" pointer to the previous node of "p"
17         ListNode *p = head, *pre = head, *last = head;
18         // "length" holds the length of linked list
19         int length = 0;
20         while (last->next != NULL) {
21             last = last->next;
22             length++;
23         }
24         length++;
25         while (p != NULL && length--) {
26             // if "p->val" is greater than or equal to x
27             if (p->val >= x) {
28                 ListNode *q = p;
29                 // if "q" is the first node
30                 if (q == head) {
31                     head = q->next;
32                     p = head;
33                 } else if (q == last) { // if "q" is the last node
34                     break;
35                 } else { // otherwise
36                     pre->next = q->next;
37                     p = pre->next;
38                 }
39                 // update "last"
40                 last->next = q;
41                 q->next = NULL;
42                 last = q;
43             } else {
44                 pre = p;
45                 p = p->next;
46             }
47         }
48         
49         return head;
50     }
51 };