Split A Circular Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
17 upvotes
Asked in companies
AdobeSamsung

Problem statement

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.

example

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 2 3 4
2
1 2
Sample Output 1 :
1 2
3 4
1
2
Explanation for sample input 1 :
Test Case 1: Refer to the example described above.

Test Case 2:
    The given circular linked list will be splitted as follows:

Test case 2

    Here 1 and 2 will point to themselves as they are the only nodes in the circular linked list.
Sample Input 2 :
2
6
2 4 3 5 2 1
4
1 1 1 1
Sample Output 2 :
2 4 3
5 2 1
1 1
1 1
Hint

Find the middle node and split.

Approaches (2)
Middle node by counting

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.
Time Complexity

O(N) per test case, where N is the number of nodes in the circular linked list.

 

In the worst case, we will be traversing the circular linked list twice.

Space Complexity

O(1).

 

In the worst case, we are using constant extra space.

Code Solution
(100% EXP penalty)
Split A Circular Linked List
Full screen
Console