Split a Circular Linked List in 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.

Input : 2 ->13 ->5 ->15 ->6 ->16

Output :

Sublist 1 is: 2 ->13 ->5
Sublist 2 is: 15 ->6 ->16

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)

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.

[code language=”cpp”]

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

[/code]

 

Please Login/Signup to comment