Linked list partition

Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

C++:
01 void enList(Node** head, Node*& tail, Node* toAdd)
02 {
03     if(*head){
04         tail->next=toAdd;
05         tail=toAdd;
06     }
07     else
08         *head=tail=toAdd;
09 }
10 
11 void linkedListPartition(Node** head, int k)
12 {
13     Node* small=NULL;
14     Node* big=NULL;
15     Node* tmp=*head;
16     Node* s=NULL;
17     Node* b=NULL;
18     while(tmp){
19         if(tmp->value<k)
20             enList(&small,s,tmp);
21         else
22             enList(&big,b,tmp);
23         tmp=tmp->next;
24     }
25     if(b)
26         b->next=NULL;
27     if(s){
28         s->next=big;
29         *head=small;
30     }
31     else
32         *head=big;
33 }
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