Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

类似于qsort的partition的思想，用两根指针记录左右两边。

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         // Start typing your C/C++ solution below13         // DO NOT write int main() function14         if (head == NULL)15             return NULL;16             17         ListNode *pPre = NULL;18         ListNode *p = head;19         ListNode *q = head;20         21         while(q->next)22             q = q->next;23             24         ListNode *tail = q;25         26         while(p != q)27         {28             if (p->val >= x)29             {30                 ListNode *pNext = p->next;31                 if (head == p)32                     head = pNext;33                 tail->next = p;34                 p->next = NULL;35                 tail = p;36                 if (pPre)37                     pPre->next = pNext;38                 p = pNext;39             }40             else41             {42                 pPre = p;43                 p = p->next;44             }45         }46         47         if (p->val >= x && q != tail)48         {49             ListNode *pNext = p->next;50             if (head == p)51                 head = pNext;52             tail->next = p;53             p->next = NULL;54             if (pPre)55                 pPre->next = pNext;56         }57         58         return head;       59     }60 };