C++ program to split a circular linked list into two halves
February 21, 2023
How to split a circular liked list into two halves in C++?
To write a C++ program to split a circular linked list into two halves, we will be finding the middle of the given list first. In order to find the middle of the list we will use the slow and fast pointer trick. And after finding the middle of the list we will make two heads in the list as each part of the list will have its own head. Further in this article we will discuss steps and algorithm two find the middle of the list and make two heads and divide the list into two halves.
Steps to split a circular linked list into two halves in CPP
Define the circular linked list in your program.
Create some basic functions like to build and display the circular liked list.
Now create a function to split the list into two halves.
In this function find the middle of the list using the slow and fast pointer trick.
Now when list will be divided into two halves there will be two heads.
So, make the node pointed by fast pointer as first head.
Make the node pointed by slow pointer as second head.
Display both the halves to the user.
struct node {int num;struct node *next;}
Algorithm to split circular linked list into two halves in C++
#include<iostream>
using namespace std;
struct Node
{
int num;
struct Node *next;
} *head;
void insertStart (struct Node **head, int data) //function to create linked list
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->num = data;
// if its the first node being entered
if (*head == NULL)
{
*head = newNode; // assigning itself as head
(*head)->next = *head; // assigning itself as next node
cout << newNode->num << " Inserted\n";
return;
}
// if CLL already as >=1 node
struct Node *curr = *head;
// traverse till last node in CLL
while (curr->next != *head)
{
curr = curr->next;
}
curr->next = newNode; // last node's next as this new node
newNode->next = *head; // new node's next as current head node
*head = newNode; // changing head node to this new node
cout << newNode->num << " Inserted\n";
// previous head node becomes 2nd node
}
void display (struct Node *head)
{
//cout << "\nCircular Linked List : " << endl;
// if circular linked list is empty currently
if (head == NULL)
return;
struct Node *temp = head;
// since we need to take care of circular nature of linked list
do
{
cout << temp->num << " ";
temp = temp->next;
}
while (temp != head);
cout << endl;
}
void splitList (struct Node **head1, struct Node **head2) //function to split list into two halves
{
struct Node *slow = head;
struct Node *fast = head;
if (head == NULL)
return;
while (fast->next != head && fast->next->next != head) //finding middle of the list
{
fast = fast->next->next;
slow = slow->next;
}
if (fast->next->next == head)
fast = fast->next;
*head1 = head;
if (head->next != head)
*head2 = slow->next;
fast->next = slow->next;
slow->next = head;
}
int main () //main function
{
head = NULL;
insertStart (&head, 1);
insertStart (&head, 2);
insertStart (&head, 3);
insertStart (&head, 4);
insertStart (&head, 5);
struct Node *head1 = NULL;
struct Node *head2 = NULL;
cout << "\nCircular linked list data:\n";
display (head);
splitList (&head1, &head2);
cout << "\nFirst half data: ";
display (head1);
cout << "\nSecond half data: ";
display (head2);
return 0;
}
Login/Signup to comment