LC86 Partition List

 1 class Solution{
 2     public:
 3     ListNode* partition(ListNode* head, int x) {
 4         if(head==NULL||head->next==NULL)
 5             return head;
 6         ListNode* p1=NULL;
 7         ListNode* p2=NULL;
 8         ListNode* tail1;
 9         ListNode* tail2;
10         while(head!=NULL)
11         {
12             if(head->val<x)
13             {
14                 if(p1==NULL)
15                 {
16                     p1=head;
17                     tail1=head;
18                 }
19                 else if(p1!=NULL)
20                 {
21                     tail1->next=head;
22                     tail1=head;
23                 }
24                 tail1->next=NULL;
25             }
26             else if(head->val>=x)
27             {
28                 if(p2==NULL)
29                 {
30                     p2=head;
31                     tail2=head;
32                 }
33                 else
34                 {
35                     tail2->next=head;
36                     tail2=head;
37                 }
38                 tail2->next=NULL;
39             }
40             head=head->next;
41         }
42         if(p1==NULL)
43             return p2;
44         else
45         {
46             tail1->next=p2;
47             return p1;
48         }
49     }
50 };