Rearrange a Linked List by Separating Odd Nodes from the Even Ones

Given a linked list, rearrange it by separating odd nodes from even ones. All even nodes should come before all odd nodes in the output list and the relative order of even and odd nodes should be maintained.

 

For example,

Consider list {1, 2, 3, 4, 5, 6, 7}, rearranging it should yield {2, 4, 6, 1, 3, 5, 7}.

 
 

The problem can be solved either iteratively or recursively. Below is simple iterative implementation that do not use dummy node –

 
C++ implementation –
 

Download   Run Code

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

 


 

2. Using Dummy Nodes

We can simplify above code by using two temporary dummy nodes as the start of the odd list and even list and maintaining two pointers that always points to the last node in individual lists, so appending new nodes is easy. The dummy node gives tail something to point to initially when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing nodes from original list, and adding it to tail of even or odd list. When we are done, we rearrange the pointers so that all even nodes are followed by all odd nodes.

 
C++ implementation –
 

Download   Run Code

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

 


 

3. Using Recursion

This is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code. You probably wouldn’t want to use the recursive version for production code however, because it will use stack space which is proportional to the length of the lists.

 
C++ implementation –
 

Download   Run Code

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

 

Exercise: Modify the solution so that all odd nodes comes before all even nodes.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Mithun
Guest
Mithun

Hi,
Thanks for the post. With dummy node i have written another login can you please share your views.
Node* reArrange(Node* head)
{
if(head==NULL)
return NULL;
Node* temp=head;
int count=0;
Node* prev=NULL;
while(temp != NULL)
{
if(temp->data & 1)
{
prev=temp;
temp=temp->next;
}
else if(count==0)
{
prev->next=temp->next;
temp->next=head;
head=temp;
temp=prev;
count++;
}
else
{
prev->next=temp->next;
temp->next=head->next;
head->next=temp;
temp=prev;
}
}
return head;
}

And one more query,how do think in terms of recursion?i can understand when i read your code, but not able to come up on my own.

wpDiscuz