LeetCode:Partition List

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. 本文地址

分析：只要把比x小的节点按顺序连成一条链，比x大或等于的节点连成另一条链，然后把两条链连起来。注意一下边界情况(某条链为空)

 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         //pl指向小于x的链，pge指向大于等于x的链
13         ListNode *p = head, *pl = NULL, *pge = NULL;
14         //分别指向两条链的头部
15         ListNode *plHead = NULL, *pgeHead = NULL;
16         while(p)
17         {
18             if(p->val < x)
19             {
20                 if(pl != NULL)
21                 {
22                     pl->next = p;
23                     pl = pl->next;
24                 }
25                 else
26                 {
27                     pl = p;
28                     plHead = p;
29                 }
30             }
31             else
32             {
33                 if(pge != NULL)
34                 {
35                     pge->next = p;
36                     pge = pge->next;
37                 }
38                 else
39                 {
40                     pge = p;
41                     pgeHead = p;
42                 }
43             }
44             p = p->next;
45         }
46         
47         if(pge != NULL)pge->next = NULL;
48         if(plHead != NULL)
49         {
50             pl->next = pgeHead;
51             return plHead;
52         }
53         else
54             return pgeHead;
55     }
56 };