partition list

partition list

Easy

Go through the list, put every node in right position.

`````` 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 ) {
14         }
15         ListNode* left = NULL;
16         ListNode* right = NULL;
17         ListNode* lr = NULL;
18         ListNode* rr = NULL;
20         ListNode* q = NULL;
21         while ( p ) {
22             q = p->next;
23             if ( p->val < x ) {
24                 if ( NULL == left ) {
25                     left = p;
26                     p->next = NULL;
27                     lr = p;
28                 } else {
29                     lr->next = p;
30                     p->next = NULL;
31                     lr = lr->next;
32                 }
33             } else {
34                 if ( NULL == right ) {
35                     right = p;
36                     p->next = NULL;
37                     rr = p;
38                 } else {
39                     rr->next = p;
40                     p->next = NULL;
41                     rr = rr->next;
42                 }
43             }
44             p = q;
45         }
46         if ( !right ) {
47             return left;
48         }
49         if ( !left ) {
50             return right;
51         }
52         lr->next = right;
53         return left;
54     }
55 };``````