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.

C++:
01 void enList(ListNode*& head, ListNode*& tail, ListNode* p)
02 {
03       if(head==NULL){
04         head=tail=p;
05       }else{
06            tail->next=p;
07         tail=p;
08       }
09 }
10 
11 ListNode *partition(ListNode *head, int x)
12 {
13     if(head==NULL)
14         return NULL;
15     ListNode* fh=NULL;
16     ListNode* fe=NULL;
17     ListNode* sh=NULL;
18     ListNode* se=NULL;
19     ListNode* tmp=head;
20     while(tmp){
21         if(tmp->val<x){
22             enList(fh,fe,tmp);
23         }else{
24             enList(sh,se,tmp);
25         }
26         tmp=tmp->next;
27     }
28     if(fh==NULL){
29         se->next=NULL;
30            return sh;
31     }
32     else{
33         fe->next=sh;
34         if(se!=NULL){
35             se->next=NULL;
36         }
37         return fh;
38     }
39 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s