Last Updated: 6 Jan, 2021
Split A Circular Linked List
Easy
Asked in companies
You are given a circular linked list having N number of nodes, where N is even. You have to split this linked list into two equal-sized circular linked lists.
Here splitting means you have to make two separate circular linked lists, one for the first N/2 nodes and one for the last N/2 nodes.
For Example :
Let the circular linked list be 1, 2, 3, 4. We have to split this into two equal-sized circular linked lists.
Input format :
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains an integer ‘N’, denoting the number nodes in the circular linked list.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the circular linked list.
Output format :
For each test case, both the circular linked lists are printed in separate lines after splitting.
The output for each test case is printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
2 <= N <= 10000, N is even
-10 ^ 9 <= node data <= 10 ^ 9
Where ‘node data’ is the value of nodes of the list.
Time limit: 1 sec
Approaches
The simple approach would be finding the middle point of the circular linked list and changing the pointers.
- Find the middle point of the circular linked list by first counting the number of nodes in the circular linked list then traversing half of them from the head.
- To make the second half of the circular linked list connect the last node, which is just before head, to the next of the middle node of the circular linked list.
- To make the first half of the circular linked list connect the middle node of the circular linked list to the head of the circular linked list.
The simple approach would be finding the middle point of the circular linked list and changing the pointers. To do so in a single iteration, the concept of slow and fast pointer is used.
- Find the middle point of the circular linked list using two pointers, where the 1st pointer will be traversing at twice the speed of the 2nd pointer.
- Stop when the 1st pointer reaches two nodes prior to the head pointer.
- To make the second half of the circular linked list connect the last node, which is just before the head, to the next of the 2nd pointer which is the middle of the circular linked list. Here, the last node will be the next node of the 1st pointer.
- To make the first half of the circular linked list connect the 2nd pointer which is the middle of the circular linked list to the head of the circular linked list.