Home » Technical Interview Questions » LinkedList Interview Questions » 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.

### 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.

### Algorithm working Example   ## C++ Prpgram

```#include <bits/stdc++.h>
using namespace std;

struct LL{
int data;
LL *next;
};

{
curr->data=dataToBeInserted;
curr->next=NULL;

else
{
}

//O(1) constant time
}

void alternatingSublist(struct LL**head,struct LL ** a, struct LL ** b)
{
struct LL * temp = *head , *A = *a , *B = *b;

bool listA = true; //decides if the present node goes into list A or not

while(temp != NULL)
{
if(listA)
{
if(A == NULL) //if first node then create node
{
*a = new LL;
(*a)->data = temp->data;
(*a)->next = NULL;
A = *a;
}

else //else create the node for next and then move to the next one
{
A->next = new LL;
A = A->next;
A->data = temp->data;
A->next = NULL;
}

}
else
{
if(B == NULL) //if first node then create node
{
*b = new LL;
(*b)->data = temp->data;
(*b)->next = NULL;
B = *b;
}

else //else create the node for next and then move to the next one
{
B->next = new LL;
B = B->next;
B->data = temp->data;
B->next = NULL;
}

}

listA = !listA; //alternate lists
temp = temp->next; // move to next node
}

}

{
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

struct LL *head = NULL; //initial list has no elements

cout<<"\nCurrent List is :-\n";

struct LL * A = NULL , *B = NULL;

cout<<"\nAfter the alternate spliting the new sublists are :\n";

cout<<"\nSubList  A is :-\n";
display(&A);

cout<<"\nSubList B is :-\n";
display(&B);

return 0;
}```