Split linked list into two lists where each list containing alternating elements from it

Given a linked list, split its into two lists where each list containing alternating elements from the original list. The elements in the new lists may be in any order.

 

For example, if the original list is {a, b, a, b, a}, then one sublist should be {a, a, a} and the other should be {b, b}.

 


 

The simplest approach iterates over the source list and use MoveNode() to pull nodes off the source and alternately put them on ‘a’ and b’. The only strange part is that the nodes will be in the reverse order that they occurred in the source list.

 
C++ implementation –
 

Download   Run Code

Output:

First List – 7 -> 5 -> 3 -> 1 -> null
Second List – 6 -> 4 -> 2 -> null

 

Using Dummy Nodes

Here is an alternative approach which builds the sub-lists in the same order as the source list. The code uses a temporary dummy header nodes for the ‘a’ and ‘b’ lists as they are being built. Each sublist has a “tail” pointer which points to its current last node — that
way new nodes can be appended to the end of each list easily. The dummy nodes give the tail pointers something to point to initially. The dummy nodes are efficient in this case because they are temporary and allocated in the stack.

 
C++ implementation –
 

Download   Run Code

Output:

First List – 1 -> 3 -> 5 -> 7 -> null
Second List – 2 -> 4 -> 6 -> null


 

Using Recursion

This problem can be easily solve by recursion as well. Below is its recursive implementation.

 
C++ implementation –
 

Download   Run Code

Output:

First List – 1 -> 3 -> 5 -> 7 -> null
Second List – 2 -> 4 -> 6 -> null

 
Exercise:
Modify the solution to use “local references” technique to get rid of the dummy nodes

 
Source:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
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
wpDiscuz