Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

Split a Circular Linked List into Two Halves

Introduction

This blog covers a linked list problem. Linked lists are one of the most essential and often asked data structures in programming contests and technical interviews. There are various standard linked list problems and techniques. This blog tackles a coding task that explores how to split a circular linked list into two halves.

Problem Statement

We are given a Circular Linked List of length n. We have to split the circular linked list into two halves. If the given circular linked list has odd numbers of nodes then the first list should contain one extra node.

Sample Examples

Input

Given Circular Linked List:

Output

First List:

Second List:

Explanation

The initial list of 4 nodes is broken into two separate two lists of equal lengths of 2 nodes each.

Input

Given Circular Linked List:

Output

First List:

Second List:

Explanation

The initial list of 5 nodes is broken into two separate lists of lengths of 2 and 3 nodes each. If the given Circular linked list has an odd number of nodes the first resultant linked list will have one node more than the second resultant circular linked list.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Approach

For the given problem, we follow a very interesting approach. We use the slow and fast pointer technique to split the list into two halves by finding the middle node of the list.

After finding the middle node we make the node pointed by the fast pointer the first head and the node pointed by the slow pointer the head of the second half list.

Initial Circular Linked List

Result Linked List 1

Result Linked List 2

Algorithm

1. Define a circular linked list to be split in half.

2. Create some basic functions, such as creating and displaying a circular liked list.

3. Create a function to divide the list in half.

4. Find the middle of the circular linked list by using the slow and fast pointer trick in this function.

5. When the list is divided in half, there will be two heads.

6. Now, make the node pointed by the fast pointer the first head.

7. The node pointed by the slow pointer will be the second head

8. Finally, display both halves to the user.

Also read - Merge sort in linked list

Implementation

``````// Program for splitting a circular linked list into two halves
#include <bits/stdc++.h>
using namespace std;

/* Node Structure */
class Node
{
public:
int x;
Node *next;
};

/* Function to split a list (starting with head)
into two lists. */
void listSplitter(Node *head, Node **h1,
Node **h2)
{
Node *slowPtr = head;
Node *fastPtr = head;
if (head == NULL)
return;

/* If there are odd nodes in the circular linked list then
fastPtr->next becomes head and for even nodes
as in case of odd number of nodes first list will contain one node
more than second list*/
while (fastPtr->next != head &&
{
fastPtr = fastPtr->next->next;
slowPtr = slowPtr->next;
}

if (fastPtr->next->next == head)
fastPtr = fastPtr->next;
*h2 = slowPtr->next;
fastPtr->next = slowPtr->next;
}

/* UTILITY FUNCTIONS */
void pushNode(Node **head, int x)
{
Node *ptr1 = new Node();
Node *temp = *head;
ptr1->x = x;

/* If linked list is not equal to NULL then
set the next of last node */
if (*head != NULL)
{
while (temp->next != *head)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1;
}

/* Function to print nodes in
a given Circular linked list */
{
string s;
Node *temp = head;
if (head != NULL)
{
cout << endl;
do
{
string p = to_string(temp->x);
s+=p;
s.push_back('-');
s.push_back('>');
temp = temp->next;
} while (temp != head);
}
s.pop_back();
s.pop_back();
cout<<s<<endl;
}

// Driver Code
int main()
{
int listSize, i;
/* Initialize empty linked lists */
Node *head = NULL;
Node *h1 = NULL;
Node *h2 = NULL;
/* Created linked list will be 12->16->24->10 */
cout << "Given Circular Linked List:";
/* Splitting the list */
cout << "\nFirst Resultant Circular Linked List:";
listPrinter(h1);
cout << "\nSecond Resultant Circular Linked List:";
listPrinter(h2);
return 0;
}``````

Output

Time Complexity

The time complexity of the above approach is O(N), where N is the number of nodes in the linked list.

We have to traverse each node of the linked list to split it into two halves.

Space Complexity

The space complexity of the above approach is O(n).

It's due to the fact that two linked lists of length n/2 are created in this method.

What happens if there are odd numbers of nodes in the given circular linked list?

If there are an odd number of nodes in the linked list the first list will have one node more than the second resultant list.

How do we find the middle of the circular linked list?

We find the middle of the circular linked list by using the slow and fast pointer trick.

How do we traverse the linked list?

We can traverse the linked list by following the next pointer in the node structure.

What is the time complexity of the above approach and why?

The time complexity of the above approach is O(N). Itâ€™s due to the fact that we have to traverse each node of the linked list to split it into two halves.

Conclusion

This article extensively discussed the problem of splitting a circular linked list into two halves and the usage of the slow and fast pointer method in these types of problems.

We hope this blog has helped you improve your knowledge regarding Linked Lists. After reading about this linked list problem, are you not feeling excited to read/explore more articles on this topic? Don't worry, Coding Ninjas has you covered. To learn, see article on linked lists here.

To study more about Linked Lists, refer to Applications Of Linked Lists.

Refer to our Guided Path on Coding Ninjas Studio to upgrade yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and much more! If you want to test your proficiency in coding, you may check out the mock test series and take part in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Topics covered
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.