Split a Circular Linked List into Two Halves

Given a circular linked list, write a program to split the circular linked list into two halves (lists).

If there are odd number of nodes, then first list will have more number of nodes than the second list.

Example

Input : 23 ->1 ->50 ->15 ->16 ->6

Output :

Sublist 1 is: 23 ->1 ->50
Sublist 2 is: 15 ->16 ->6

In this method, we will split the circular linked list into two halves by returning the pointer to the second half of the list

Time Complexity : O(n)

Algorithm

1. Store the mid and last pointers of the circular linked list. Create two pointers fast, slow and point them to head.
    a. Increment fast 2 times and slow 1 time till fast's next or fast's next next reach the head    
    pointer again.
    b. Now, fast will point to the last or last but one node of the list and the slow will point to the mid of the list
    c. Using fast and slow divide the circular list into two halves, by returning the head address for list1 and slow's next address for list2

2. Set the start pointers of two linked lists, one pointing to head of the list and the other to mid.

Implementation of spliting a circular linked list into two halves

 

C++ Program

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

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


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

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

void splitCircular(struct LL *head, struct LL **list1, struct LL **list2) {
	if(!head) 
		return;	
	
	struct LL *slow = head, *fast = head;
	
	while(fast->next != head && fast->next->next != head) {
		slow = slow->next;
		fast = fast->next->next;
	}
	
	fast->next == head ? fast->next = NULL : fast->next->next = NULL;
	*list1 = head;
	*list2 = slow->next;
	slow->next = NULL;
}

int main() {
		
	struct LL *head = NULL;
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,47);

	
	cout<<"Current List is :-\n";
	display(&head);
	
	head->next->next->next->next->next->next->next = head; //Made the list Circular
	
	struct LL *list1 = NULL, *list2 = NULL;
	splitCircular(head, &list1, &list2);
	
	cout<<"\n After splitting circular linked list the two sublists are \n";
	cout<<"\nSublist 1 is :-\n";
	display(&list1);		
	
	cout<<"\nSublist 2 is :-\n";
	display(&list2);		
	
	
	return 0;
}
Try It


Next > < Prev
Scroll to Top