Rearrange the linked list in specific manner

Given a linked list, split it into two lists where each list contains alternating elements from the original list and then finally join them back together.


For example,

Input  : 1 -> 2 -> 3 -> 4 -> 5 -> null
Output : 1 -> 3 -> 5 -> 2 -> 4 -> null



To split the given list into two, we can use temporary dummy header nodes for the both 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. Finally after both lists are formed, we join them by rearranging their pointers and also fix the head node.

C++ implementation –

Download   Run Code


1 -> 3 -> 5 -> 2 -> 4 -> null


The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

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 🙂