How to split a circular linked list into two halves?

You need to divide a circular linked list with divisions of the same size. If the circular linked list is odd, you must change the number of nodes. It is an even number. Explain with pictures. See the picture below.

split

Algorithm:

  1. First count the number of nodes in the Circular Link List // The way to divide the list is the Floyd algorithm, which is much better.
  2. Next, you need to match the list.
  3. Third, I cut the list in half. The front is the same size as the rear. Finally, we need to create two circular linked lists.
struct node 
 {
   int data;
   struct node *next;
 };
 void SplitList (struct node * head, struct node **head1_ref, struct node **head2_ref) {
      struct node * fastNode = head;
      struct node * slowNode = head;
      
      if (head == NULL)
       return;
      while (fastNode -> next != head && fastNode -> next -> next != head) {
          fastNode = fastNode -> next -> next;
          slowNode = slowNode -> next;
      }
      if (fastNode -> next -> next == head)
           fastNode = fastNode -> next;
      *head1_ref = head;
      if (head -> next != head)
       *head2_ref = slowNode -> next;
      fastNode -> next = slowNode -> next;
      slowNode -> next = head;
 }
Below is a complete program that how to split a circular linked list into two halves using the above methods.

For example:

split

split

split

split

Here Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
          public:
          int data;
          Node *next;
};
void splitList(Node *head, Node **head1_ref,Node **head2_ref)
{
          Node *slow_ptr = head;
          Node *fast_ptr = head;
          if(head == NULL)
                   return;
          while(fast_ptr->next != head &&
                   fast_ptr->next->next != head)
          {
                   fast_ptr = fast_ptr->next->next;
                   slow_ptr = slow_ptr->next;
          }
          if(fast_ptr->next->next == head)
                   fast_ptr = fast_ptr->next;
          *head1_ref = head;
          if(head->next != head)
                   *head2_ref = slow_ptr->next;
          fast_ptr->next = slow_ptr->next;
          slow_ptr->next = head;
}
void push(Node **head_ref, int data)
{
          Node *ptr1 = new Node();
          Node *temp = *head_ref;
          ptr1->data = data;
          ptr1->next = *head_ref;
          if(*head_ref != NULL)
          {
                   while(temp->next != *head_ref)
                   temp = temp->next;    
                   temp->next = ptr1;
          }
          else
                   ptr1->next = ptr1;
          *head_ref = ptr1;
}
void printList(Node *head)
{
          Node *temp = head;
          if(head != NULL)
          {
                   cout << endl;
                   do {
                   cout << temp->data << " ";
                   temp = temp->next;
                   } while(temp != head);
          }
}
int main()
{
          int list_size, i;
          Node *head = NULL;
          Node *head1 = NULL;
          Node *head2 = NULL;
          push(&head, 12);
          push(&head, 56);
          push(&head, 2);
          push(&head, 11);
          cout << "Original Circular Linked List";
          printList(head);
          splitList(head, &head1, &head2);
          cout << "\nFirst Circular Linked List";
          printList(head1);
          cout << "\nSecond Circular Linked List";
          printList(head2);
          return 0;
}

Recommended Articles:

  1. Traversal in Circular Linked List
  2. C++ program to insert in a sorted circular linked list?
  3. How to reverse a string using stack?
  4. Insertion in Circular Singly Linked List
  5. How to swap nodes in a linked list without Swapping data?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 134 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
9 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

trackback

[…] How to split a circular linked list into two halves? […]

You cannot copy content of this page
Scroll Up
9
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.