C++ program to split a circular linked list into two halves

Split the circular linked list into two halves in C++

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

These steps are followed in C++ programming to split a circular linked list into two halves

  1. Define the circular linked list in your program.
  2. Create some basic functions like to build and display the circular liked list.
  3. Now create a function to split the list into two halves.
  4. In this function find the middle of the list using the slow and fast pointer trick.
  5. Now when list will be divided into two halves there will be two heads.
  6. So, make the node pointed by fast pointer as first head.
  7. Make the node pointed by slow pointer as second head.
  8. Display both the halves to the user.
Constuct circular linked list

How to build nodes of a in C++?

class Node  

    int data; 
    Node *next; 
}; 
C++ program to split a circular linked list into two halves

Algorithm  to split circular linked list into two halves in C++

This algorithm is followed in C++ programming to split circular linked list into two halves

  • STRUCT NODE SLOW = HEAD
  • STRUCT NODE FAST = HEAD
  • IF HEAD==NULL
  • RETURN
  • WHILE(FAST->NEXT !=HEAD&&FAST->NEXT->NEXT!= HEAD)
  • FAST=FAST->NEXT->NEXT
  • SLOW=SLOW->NEXT
  • END WHILE
  • IF FAST->NEXT->NEXT==HEAD
  • FAST=FAST->NEXT
  • HEAD1 = HEAD
  • IF FAST->NEXT != HEAD
  • HEAD2=SLOW->NEXT
  • FAST->NEXT=SLOW->NEXT
  • SLOW->NEXT=HEAD

C++ program for splitting the circular linked list into two halves

#include <iostream>
using namespace std;

struct node {
    int num;
    struct node * next;
}*head;
void build(int n)//function to build linked list
{
    int i, num;
    struct node *preptr, *newnode;

    if(n >= 1)
    {
        head = (struct node *)malloc(sizeof(struct node));

        cout<<"Enter data of the list:\n";
        cin>>num;
        head->num = num;
        head->next = NULL;
        preptr = head;
        for(i=2; i<=n; i++)
        {
            newnode = (struct node *)malloc(sizeof(struct node));
            cin>>num;
            newnode->num = num;
            newnode->next = NULL;	
            preptr->next = newnode;	
            preptr = newnode;   		
        }
        preptr->next = head;//linking last node with head node
    }
}
void display(struct node *head)//function to display list
{
    struct node *tmp;
    int n = 1;
    
    if(head == NULL)
    {
        cout<<"List is empty";
    }
    else
    {
        tmp = head;
        
        
        do {
            cout<<tmp->num<<" ";
            tmp = tmp->next;
            n++;
        }while(tmp != head);
    }
}
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
{
    int n;
    struct node *head1 = NULL; 
    struct node *head2 = NULL;
    head = NULL;
    cout<<"Enter the size of circular linked list: ";
    cin>>n;
    build(n); 
    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;
}
Output:
Enter the size of circular linked list: 6
Enter data of the list:
99
98
97
96
95
94

Circular linked list data:
99 98 97 96 95 94 
First half data: 99 98 97 
Second half data: 96 95 94

Want to learn more Data Structure?