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

Output:

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

Java

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

Output:

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

Java

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

Output:

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

Java

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.

(1 votes, average: 5.00 out of 5)