Home » Technical Interview Questions » LinkedList Interview Questions » Split linked list using alternate nodes

Split linked list using alternate nodes


Reading Time - 4 mins

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;
}

READ  Implementation of Deque using Doubly Linked List
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions