Split a circular linked list in two halves in C

Sentences that can be formed from the list of words

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.

Split a circular linked list in two halves

Circular linked list has also this topic that how to split linked list in two halves,basically in this topic we want to do the linked list should be split in two halves either in odd or even node.

you have to split the circular Linked List with the same size of Divisions.

Maybe if circular Linked List is odd, you have to change the number of node, it is even .

Implementation In split a circular linked list

  • So basically we have a circular linked list where we have the six element,so in the answer we should have two list first list  should contain be first element then third then fifth then seven and second list should contain  second element, fourth element the six.
  • In the list have element is 11,89,9,29,7,75 total six element in the circular linked list.
  • we will have  two variable first will have the first head usually called to the first head of the list and second head which will point to the node of next.
  • Now we will have two temporary   variable first temp or second temp ,so will start the loop from here which is a node first temp of next should point to next which is 9 and second temp of next should point to node of next,
  • and we will iterate the loop until we will reach the node of null,and after the complete loop, so will skip the  loop.
Split a circular linked list in two halves in C-1

Algorithm

  • First count the number of node in Circular Linked List.
  • Second, I have to make the List even.
  • Third, I make the List half. the front is the same size like the rear. Finally, I have to make two circular Linked List.

Code For Split a Circular Linked List

Run
#include<stdio.h>
#include<stdlib.h>
struct Node
{
  int data;
  struct Node *next;
};

//function to split list into two halves
void splitList (struct Node *head, struct Node **head1, struct Node **head2)
{
  struct Node *slow = head;
  struct Node *fast = head;

  if (head == NULL)
    return;

  //finding middle of the list 
  while (fast->next != head && fast->next->next != head)
    {
      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;
}

void insertStart (struct Node **head, int data)
{
  struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
  newNode->data = data;

  // if its the first node being entered
  if (*head == NULL)
    {
      *head = newNode;
      (*head)->next = *head;
      return;
    }

  struct Node *curr = *head;

  // traverse till last node in LL
  while (curr->next != *head)
    {
      curr = curr->next;
    }

  curr->next = newNode;
  newNode->next = *head;
  *head = newNode;
}

void display (struct Node *head)
{
  // if there are no node in LL
  if (head == NULL)
    return;

  struct Node *temp = head;

  //need to take care of circular structure of LL
  do
    {
      printf ("%d ", temp->data);
      temp = temp->next;

    }
  while (temp != head);
  printf ("\n");
}

int main ()				//main function
{
  struct Node *head = NULL;
  struct Node *head1 = NULL;
  struct Node *head2 = NULL;

  insertStart (&head, 6);
  insertStart (&head, 5);
  insertStart (&head, 4);
  insertStart (&head, 3);
  insertStart (&head, 2);
  insertStart (&head, 1);

  printf ("Linked List is: ");
  display (head);

  splitList (head, &head1, &head2);

  printf ("\nFirst half data: ");
  display (head1);

  printf ("\nSecond half data: ");
  display (head2);
  return 0;
}

Output:

Linked List is: 1 2 3 4 5 6 

First half data: 1 2 3 

Second half data: 4 5 6 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • Insertion in Circular Linked List –
    C | C++ | Java
  • Insertion at the beginning–
    C | C++ | Java
  • Insertion at the end –
    C | C++ | Java
  • Insertion at nth position –
    C | C++ | Java
  • Deletion in Circular Linked List –
    C | C++ | Java
  • Deletion from beginning in Circular Linked List –
    C | C++ | Java
  • Deletion from nth position in Circular Linked List –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in Circular Linked List – C | C++ | Java
  • Split a Circular Linked List in two halves –
    C | C++ | Java
  • Count nodes in Circular Linked List –
    C | C++ | Java
  • Sorted Insert In Circular Linked List –
    C | C++ | Java
  • Insertion in the middle in Circular Linked List –
    C | C++ | Java

Circular Linked List