Problem Statement:
You are given an circular LL, you need to convert into 2 halves.
Example
Input: -> 1 -> 2 -> 3 -> 4 ^ | | _ _ _ _ _| Output: -> 1 -> 2 ^ | | _ _| -> 3 -> 4 ^ | | _ |
Solution
We store the mid and last pointers of circular linked list using 2 pointers method
Then make the second half circular LL
Then first half circular LL
Then set the head pointers of two LL
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> using namespace std; class Node { public: int data; Node *next; }; void split_circular_list(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 print_list(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; /* Created linked list will be 1->5->2->8 */ push(&head, 1); push(&head, 5); push(&head, 2); push(&head, 8); cout << "Original Circular Linked List"; print_list(head); split_circular_list(head, &head1, &head2); cout << "\nFirst Circular Linked List"; print_list(head1); cout << "\nSecond Circular Linked List"; print_list(head2); return 0; }
Output:
Original Circular Linked List 8 2 5 1 First Circular Linked List 8 2 Second Circular Linked List 5 1