Split linked list using alternate nodes

Split linked list using alternate nodes

Given a linked list, you need to split it into two linked lists with alternate elements in each of them.


Input linked list

1 → 9 → 3 → 7 → 4 → 6 → Null

Output lists will be

1 → 3 → 4 → Null
9 → 7 → 6 → Null


Time complexity : O(n)

Step 1 : create alternating sub list function which takes a linked list and elements into two other linked lists with alternate elements from the linked list in it.
Step 2 : Create two empty linked lists. So that we can add elements into them.
Step 3 : In this function, we initialize a variable ListA equal to true,
a)    Until the given list is not empty, we traverse in Linked list such that, if ListA equal to true we add the element in list 1 if false add in list 2. But after adding an element we change the value of ListA(true to false and false to true).
b)    Changing the value ofListA makes the elements in the linked list such that elements which are next to each other will not be added in the same new list that we created.
Step 4 : To check this, create two new empty linked lists and call the function on then linked list and print the new linked lists.

Algorithm working Example