Introduction: In this article, we will solve a problem titled “Split a circular Linked List into two halves”.
What is a Linked List?
A linked list is a data structure that can be used to store non-contiguous data. What does it mean? It means that, unlike an array, a linked list does not have all the elements placed contiguously in the memory. Let us have a look at the diagram given below:
The diagram above shows an array of size 6. It is given that the base address is 2000 i.e. the address of the first element of the array is 2000 and the size of the int data type is 4 bytes. Hence, the array has a contiguous memory as shown above. The first element starts from the memory block with the address of 2000 and ends at 2003 (size = 4 bytes). So, for contiguous memory allocation, the next element starts from the very next memory location i.e 2004 and this goes on for the rest of the elements too.
What if we do not have that much contiguous space? This means that overall memory is available but the amount of contiguous memory that we require to create an array is not available.
This condition in which the memory is available in fragments and not contiguously is called fragmentation. So, when fragmentation occurs, we can store the data in a linked list as shown below:
The data inside a linked list is stored in a node as shown above. Each node has 2 parts. One is the ‘data’ field where the data is stored and the other field is the ‘next’ field where the address of the next node is stored. We need to store the address of the next node as the data is not contiguous and we don’t know where the next data of the sequence will be.
So, you can see that the addresses are in random order. Each node points to the next node because of the address of the next node stored within itself.
Since the linked list is connected completely like a chain, in order to know all the elements of the linked list, we just need to know the address of the first node (as the rest can be reached from the first node by traversing using the next pointer). So, the address of the first node is called the head of the linked list. It can be said that a linked list can be identified if we have its head. The last node of the linked list (whose next stores null) is often called the tail of the linked list.
What is a Circular Linked List?
When the tail of a linked list points to its head instead of storing null in its next pointer, a linked list becomes circular. This is shown in the diagram given below:
So, there is no endpoint or last node, or tail in such a linked list. If we start traversing a circular linked list, we keep on moving in it forever (unless we decide to stop on some condition) as there is no node whose next is null.
View Website
View Website
View Website
So, now that we have got a good idea of what a linked list is and what a circular linked list is, let us move to our problem.
Problem Statement
Given a Circular Linked List, split it into 2 halves such that if there are even elements, there should be equal elements in both the halves and if there are odd elements, the first half should contain one element more as compared to the second half.
Example
So, the odd-sized linked list was split into 2 halves, the first one being the larger (as per the problem statement).
Approach
Let us discuss the approach to solve this problem:
Hare and Tortoise Algorithm (Two Pointer)
Let us consider the circular linked list shown in the problem statement.
In order to split the linked list into two halves, we first need to know where the linked list is ending and where is the middle of the linked list. Why? Let us say that we got to know the middle and the tail of the linked list. Then, we can split the linked list into two halves as shown below:
For the case of even number of nodes in a linked list, the same procedure will be applied as shown below:
So, the question boils down to finding the middle of a Circular Linked List in such a way that the function that we use to find the middle, gives the middle node of the odd-sized Circular Linked List and it gives the last node of the first half as the middle node in an even sized Circular Linked List.
Also, we need to find the tail too as we have to point the next of the tail to the head2 as shown above.
Finding the Tail
Let us look at the diagram shown below:
We have a pointer p which initially points at the head of the circular linked list. Now, we move the pointer p till we reach the tail of the circular linked list. The tail of the circular linked list can be identified as follows: When the pointer p reaches the tail of the linked list, its next points to the head of the list. Hence, we have to move the p pointer ahead till the next of the p becomes head.
Now, all we have to learn is the method to find the middle of the circular linked list.
Middle of the Linked List (Hare and Tortoise Approach)
We will have 2 pointers, slow and fast both at the head of the linked list. The slow pointer moves 1 step at a time and the fast pointer moves 2 steps at a time. When the fast pointer reached the end (we will discuss what the end would be), the slow pointer will be on the middle of the linked list.
Note: We also have to take care that for even number of nodes in the linked list, the middle should be at the last node of the first half.
Let us see the diagram for the case of odd number of nodes shown below:
So, as you can see, we moved the slow pointer one step and the fast pointer 2 steps at a time. When the fast pointer reaches the tail i.e. fast.next = head, the slow pointer is at the middle of the linked list.
Now, let us see the case for an even number of nodes in the linked list.
Since we have to return the last node of the first half of the linked list when we have an even number of nodes, we can say that when fast reaches one node previous to the tail i.e. when fast.next.next = head, slow is at the middle node.
So, now we know the conditions for finding the middle of the linked list, and also, we know what to do after we have the middle and tail of the linked list. This is the procedure to split a circular linked list into 2 halves.
Algorithm (In short)
Find the tail and the middle of the circular linked list. The tail of the linked list can be found using iteration and middle using the hare and tortoise technique. Now, head1 = head and head2 = middle.next Middle.next = head1 and tail.next = head2 We have split the linked list into two halves.
So, now that we are clear with the algorithm, let us look at the code for the same
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next; //self referential pointer
};
//Here, head is the head of the current linked list.
// We will store the heads of the 2 linked lists that
//we get on splitting in head1 and head2 respectively
void split(Node *head, Node **head1,Node **head2)
{
Node *slow = head;
Node *fast = head;
//if the linked list is empty
//we can't split it
if(head == NULL)
return;
Node *tail = head;
//finding the tail of the LL
while(tail->next != head) {
tail = tail->next;
}
//finding the middle of the LL
while(fast->next != head && fast->next->next != head)
{
//move fast 2 steps at a time
fast = fast->next->next;
//move slow 1 step at a time
slow = slow->next;
}
Node *middle = slow;
//set head1 and head2 and split
//LL in 2 circular halves
*head1 = head;
*head2 = middle->next;
tail->next = *head2;
middle->next = *head1;
}
//Utility functions for creation and display of LL
void push(Node **head, int data)
{
Node *ptr = new Node();
Node *temp = *head;
ptr->data = data;
ptr->next = *head;
if(*head != NULL)
{
while(temp->next != *head)
temp = temp->next;
temp->next = ptr;
}
else
ptr->next = ptr;
*head = ptr;
}
void displayCircularList(Node *head)
{
Node *ptr = head;
cout<<ptr->data<<" ";
ptr = ptr->next;
while(ptr != head) {
cout<<ptr->data<<" ";
ptr = ptr->next;
}
cout<<"\n";
}
// Driver Code
int main()
{
int n;
/* Initialize lists as empty */
Node *head = NULL;
Node *head1 = NULL;
Node *head2 = NULL;
cin>>n; //number of elements in the LL
for(int i=1;i<=n;i++) {
int ele;
cin>>ele;
push(&head,ele);
}
cout << "Given Circular Linked List\n";
displayCircularList(head);
//Splitting the List
split(head, &head1, &head2);
cout<<"After splitting\n";
cout << "First Circular Linked List\n";
displayCircularList(head1);
cout << "Second Circular Linked List\n";
displayCircularList(head2);
return 0;
}
Practice it on InterviewBit
C Code
#include <stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next; //self referential pointer
};
//Here, head is the head of the current linked list.
// We will store the heads of the 2 linked lists that
//we get on splitting in head1 and head2 respectively
void split(struct Node *head, struct Node **head1,struct Node **head2)
{
struct Node *slow = head;
struct Node *fast = head;
//if the linked list is empty
//we can't split it
if(head == NULL)
return;
struct Node *tail = head;
//finding the tail of the LL
while(tail->next != head) {
tail = tail->next;
}
//finding the middle of the LL
while(fast->next != head && fast->next->next != head)
{
//move fast 2 steps at a time
fast = fast->next->next;
//move slow 1 step at a time
slow = slow->next;
}
struct Node *middle = slow;
//set head1 and head2 and split
//LL in 2 circular halves
*head1 = head;
*head2 = middle->next;
tail->next = *head2;
middle->next = *head1;
}
//Utility functions for creation and display of LL
void push(struct Node **head, int data)
{
struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
struct Node *temp = *head;
ptr->data = data;
ptr->next = *head;
if(*head != NULL)
{
while(temp->next != *head)
temp = temp->next;
temp->next = ptr;
}
else
ptr->next = ptr;
*head = ptr;
}
void displayCircularList(struct Node *head)
{
struct Node *ptr = head;
printf("%d ", ptr->data);
ptr = ptr->next;
while(ptr != head) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}
// Driver Code
int main()
{
int n;
/* Initialize lists as empty */
struct Node *head = NULL;
struct Node *head1 = NULL;
struct Node *head2 = NULL;
scanf("%d",&n); //number of elements in the LL
int i=1;
for(i=1;i<=n;i++) {
int ele;
scanf("%d",&ele);
push(&head,ele);
}
printf("Given Circular Linked List\n");
displayCircularList(head);
//Splitting the List
split(head, &head1, &head2);
printf("After splitting\n");
printf("First Circular Linked List\n");
displayCircularList(head1);
printf("Second Circular Linked List\n");
displayCircularList(head2);
return 0;
}
Java Code
import java.util.*;
class Node
{
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
class CircularLinkedList
{
Node head, head1, head2;
Node last = null;
public void addToTheLast(Node node)
{
if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = node;
}
}
void displayList(Node node)
{
Node temp = node;
if(node != null)
{
do{
System.out.print(temp.data+" ");
temp = temp.next;
} while(temp != node);
}
System.out.println();
}
void makecircular()
{
last = head;
while (last.next != null)
last = last.next;
last.next = head;
}
}
public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
CircularLinkedList llist = new CircularLinkedList();
int a1=sc.nextInt();
Node head= new Node(a1);
llist.addToTheLast(head);
for (int i = 1; i < n; i++) {
int a = sc.nextInt();
llist.addToTheLast(new Node(a));
}
llist.makecircular();
System.out.println("Before Splitting");
llist.displayList(llist.head);
System.out.println("After Spliiting");
Main m = new Main();
m.splitList(llist);
System.out.println("List 1:");
llist.displayList(llist.head1);
System.out.println("List 2:");
llist.displayList(llist.head2);
}
// Function to split a circular LinkedList
void splitList(CircularLinkedList list)
{
// Your code here
Node head = list.head;
Node tail = head;
while(tail.next != head) {
tail = tail.next;
}
Node middle = getMiddle(head);
Node head1 = head;
Node head2 = middle.next;
middle.next = head1;
tail.next = head2;
list.head1 = head1;
list.head2 = head2;
}
Node getMiddle(Node head) {
Node slow = head;
Node fast = head;
while(fast.next!=head && fast.next.next != head) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Python Code
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def push(self, data):
ptr = Node(data)
temp = self.head
ptr.next = self.head
if self.head is not None:
while(temp.next != self.head):
temp = temp.next
temp.next = ptr
else:
ptr.next = ptr
self.head = ptr
def displayList(self):
temp = self.head
if self.head is not None:
while(True):
print ("%d" %(temp.data),end=' ')
temp = temp.next
if (temp == self.head):
break
def splitList(self, head1, head2):
slow = self.head
fast = self.head
if self.head is None:
return
while(fast.next != self.head and
fast.next.next != self.head ):
fast = fast.next.next
slow = slow.next
if fast.next.next == self.head:
fast = fast.next
head1.head = self.head
if self.head.next != self.head:
head2.head = slow.next
fast.next = slow.next
slow.next = self.head
head = CircularLinkedList()
head1 = CircularLinkedList()
head2 = CircularLinkedList()
n = int(input())
l = list(map(int,input().split()))
for i in range(n):
head.push(l[i])
print ("Original Circular Linked List")
head.displayList()
# Split the list
head.splitList(head1 , head2)
print ("\nFirst Circular Linked List")
head1.displayList()
print ("\nSecond Circular Linked List")
head2.displayList()
Time Complexity: The time complexity of the solution that we have discussed is O(N) where N is the number of elements in the circular linked list. This is because we have traversed the linked list twice. Once, for finding the tail and the other time for finding the middle.
Space Complexity: Since we have not used any extra space to solve the problem, the space complexity is O(1).
So, this was all about the split a Circular Linked List question. Hope that you have understood it and implemented the solution in your favorite programming language.
Comments (0)