Table of Contents
Given a linked list, you need to split it into two linked lists with alternate elements in each of them.
Example
Input linked list
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;
};
void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
struct LL*temp=*head,*curr=new LL;
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==NULL)
*head=curr;
else
{
curr->next=*head;
*head=curr;
}
//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
}
}
void display(struct LL**head)
{
struct LL*temp=*head;
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
insertAtBeginning(&head,23);
insertAtBeginning(&head,49);
insertAtBeginning(&head,73);
insertAtBeginning(&head,15);
insertAtBeginning(&head,62);
insertAtBeginning(&head,1);
insertAtBeginning(&head,116);
insertAtBeginning(&head,982);
cout<<"\nCurrent List is :-\n";
display(&head);
struct LL * A = NULL , *B = NULL;
alternatingSublist(&head , &A , &B);
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;
}