# Split linked list using alternate nodes

0
263

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

### Example

1Â â†’ 9 â†’ 3 â†’ 7 â†’ 4 â†’ 6 â†’ Null

Output lists will be

1 â†’ 3 â†’ 4 â†’ Null
9 â†’ 7 â†’ 6 â†’ Null

## Algorithm

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.