Given two circular linked lists L1 and L2, the task is to find if the two circular linked lists are identical or not.
Note: Head of any linked list points to any node of the respective linked list and the lists can contain duplicate elements.
Examples:
Input: L1: 1 -> 2 -> 3 -> 4 -> 5 -> 1 -> 2 -> 6
L2: 5 -> 1 -> 2 -> 6 -> 1 -> 2 -> 3 -> 4
Output: Identical
Explanation: If checked the 5th element of L1 and 1st element of L2 then they are identical.
As they are circular, does not matter from where we start checking.Input: L1: 1 -> 2 -> 3
L2: 1 ->3 -> 2
Output: Not Identical
Approach: The problem can be solved by traversing the circular linked list using the following idea:
This idea to solve this problem is similar to the problem “Check if given strings are rotations of each other or not“. We’ll convert given circular linked list into string and then check if second string is rotation of first string or not or vice versa.
Follow the steps below to implement the above idea:
- Convert the first circular linked list into a string say S.
- Convert the second circular linked list into a string say T.
- Check lengths of S and T are not equal
- If true, then return false.
- Store the concatenation of S with S itself in variable temp (i.e, temp = S+S).
- Check if T is a substring in temp.
- If true, then return true.
- Otherwise, return false.
Below is the implementation of the above approach:
C++
// C++ program to Check that two circular// linked list are identical or not#include <bits/stdc++.h>using namespace std;// Circular Linked list Node Classclass Node {public: int data; Node* next; // Constructor function Node(int data) { this->data = data; this->next = NULL; }};// Function to insert a node in// tail in circular linked listvoid insertNode(Node*& head, Node*& tail, int d){ // First insertion in circular // linked list if (head == NULL) { Node* newNode = new Node(d); head = newNode; tail = newNode; newNode->next = newNode; } else { // Non-empty list Node* temp = new Node(d); temp->next = tail->next; tail->next = temp; tail = tail->next; }}// Function to print circular linked listvoid print(Node* head){ Node* curr = head; // If circular linked list is empty if (head == NULL) { cout << "List is Empty " << endl; return; } // Else iterate until node is NOT head do { cout << curr->data << " "; curr = curr->next; } while (curr != head); cout << endl;}string convertString(Node* head){ Node* curr = head; string s = ""; // If circular linked list is empty if (head == NULL) { return ""; } // Else iterate until node is NOT head do { s += to_string(curr->data); s += "*"; curr = curr->next; } while (curr != head); return s;}// Function to Check that two circular// linked list are identical or notbool checkIdentical(string& S, string& T){ /* Check if sizes of two strings are same */ if (S.length() != T.length()) return false; string temp = S + S; return (temp.find(T) != string::npos);}// Driver Codeint main(){ Node* head1 = NULL; Node* tail1 = NULL; insertNode(head1, tail1, 1); insertNode(head1, tail1, 2); insertNode(head1, tail1, 3); insertNode(head1, tail1, 4); insertNode(head1, tail1, 5); insertNode(head1, tail1, 1); insertNode(head1, tail1, 2); insertNode(head1, tail1, 6); Node* head2 = NULL; Node* tail2 = NULL; insertNode(head2, tail2, 5); insertNode(head2, tail2, 1); insertNode(head2, tail2, 2); insertNode(head2, tail2, 6); insertNode(head2, tail2, 1); insertNode(head2, tail2, 2); insertNode(head2, tail2, 3); insertNode(head2, tail2, 4); cout << "First circular linked list: "; print(head1); cout << "Second circular linked list: "; print(head2); string S = convertString(head1); string T = convertString(head2); bool flag = checkIdentical(S, T); if (flag) cout << "Identical"; else cout << "Not Identical"; return 0;} |
Java
import java.util.*;public class HelloWorld { static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to insert a node in // tail in circular linked list public static List<Node> insertNode(Node head, Node tail, int d) { // First insertion in circular // linked list if (head == null) { Node newNode = new Node(d); head = newNode; tail = newNode; newNode.next = newNode; } else { // Non-empty list Node temp = new Node(d); temp.next = tail.next; tail.next = temp; tail = tail.next; } List<Node> ans = new ArrayList<Node>(); ans.add(head); ans.add(tail); return ans; } public static String convertString(Node head) { Node curr = head; String s = ""; // If circular linked list is empty if (head == null) { return ""; } // Else iterate until node is NOT head do { s += curr.data; s += "*"; curr = curr.next; } while (curr != head); return s; } // Function to print circular linked list public static void print(Node head) { Node curr = head; // If circular linked list is empty if (head == null) { System.out.println("List is Empty"); return; } // Else iterate until node is NOT head do { System.out.print(curr.data + " "); curr = curr.next; } while (curr != head); System.out.println(); } // Function to Check that two circular // linked list are identical or not public static boolean checkIdentical(String S, String T) { /* Check if sizes of two strings are same */ if (S.length() != T.length()) { return false; } String temp = S + S; if (temp.contains(T)) { return true; } return false; } public static void main(String[] args) { Node head1 = null; Node tail1 = null; List<Node> a = insertNode(head1, tail1, 1); head1 = a.get(0); tail1 = a.get(1); a = insertNode(head1, tail1, 2); head1 = a.get(0); tail1 = a.get(1); a = insertNode(head1, tail1, 3); head1 = a.get(0); tail1 = a.get(1); a = insertNode(head1, tail1, 4); head1 = a.get(0); tail1 = a.get(1); a = insertNode(head1, tail1, 5); head1 = a.get(0); tail1 = a.get(1); a = insertNode(head1, tail1, 1); head1 = a.get(0); tail1 = a.get(1); a = insertNode(head1, tail1, 2); head1 = a.get(0); tail1 = a.get(1); a = insertNode(head1, tail1, 6); head1 = a.get(0); tail1 = a.get(1); Node head2 = null; Node tail2 = null; a = insertNode(head2, tail2, 5); head2 = a.get(0); tail2 = a.get(1); a = insertNode(head2, tail2, 1); head2 = a.get(0); tail2 = a.get(1); a = insertNode(head2, tail2, 2); head2 = a.get(0); tail2 = a.get(1); a = insertNode(head2, tail2, 6); head2 = a.get(0); tail2 = a.get(1); a = insertNode(head2, tail2, 1); head2 = a.get(0); tail2 = a.get(1); a = insertNode(head2, tail2, 2); head2 = a.get(0); tail2 = a.get(1); a = insertNode(head2, tail2, 3); head2 = a.get(0); tail2 = a.get(1); a = insertNode(head2, tail2, 4); head2 = a.get(0); tail2 = a.get(1); System.out.print("First circular linked list: "); print(head1); System.out.print("Second circular linked list: "); print(head2); String S = convertString(head1); String T = convertString(head2); boolean flag = checkIdentical(S, T); if (flag) System.out.println("Identical"); else System.out.println("Not Identical"); }} |
Python3
# Python program to check that two circular# linked list are identical or not# Circular linked list node classclass Node: def __init__(self, data): self.data = data self.next = None# function to insert a node in# tail in circular linked listdef insertNode(head, tail, d): # first insertion in circular # linked list if(head is None): newNode = Node(d) head = newNode tail = newNode newNode.next = newNode else: # non-empty list temp = Node(d) temp.next = tail.next tail.next = temp tail = tail.next return head, tail# function to print circular linked listdef printList(head): curr = head # if circular linked list is empty if(head is None): print("List is Empty.") return # else iterate until node is not head while True: print(curr.data, end=" ") curr = curr.next if(curr == head): break print("")def convertString(head): curr = head s = "" # if circular linked list is empty if(head is None): return "" # else iterate until node is not head while True: s += str(curr.data) s += "*" curr = curr.next if(curr == head): break return s# function to check that two circular# linked list are identical or notdef checkIdentical(S, T): # check if sizes of two strings are same if(len(S) != len(T)): return False temp = S+S if T in temp: return True else: return False# driver programhead1 = Nonetail1 = Nonehead1, tail1 = insertNode(head1, tail1, 1)head1, tail1 = insertNode(head1, tail1, 2)head1, tail1 = insertNode(head1, tail1, 3)head1, tail1 = insertNode(head1, tail1, 4)head1, tail1 = insertNode(head1, tail1, 5)head1, tail1 = insertNode(head1, tail1, 1)head1, tail1 = insertNode(head1, tail1, 2)head1, tail1 = insertNode(head1, tail1, 6)head2 = Nonetail2 = Nonehead2, tail2 = insertNode(head2, tail2, 5)head2, tail2 = insertNode(head2, tail2, 1)head2, tail2 = insertNode(head2, tail2, 2)head2, tail2 = insertNode(head2, tail2, 6)head2, tail2 = insertNode(head2, tail2, 1)head2, tail2 = insertNode(head2, tail2, 2)head2, tail2 = insertNode(head2, tail2, 3)head2, tail2 = insertNode(head2, tail2, 4)print("First circular linked list : ")printList(head1)print("Second Circular linked list : ")printList(head2)S = convertString(head1)T = convertString(head2)flag = checkIdentical(S, T)if(flag): print("Identical")else: print("Not Identical")# This code is contributed by Kirti Agarwal(kirtiagarwal23121999) |
Javascript
// JavaScript program to check thattwo circular// linked list are identical or not// Circular linked list nodeclassclass Node{ constructor(data){ this.data = data; this.next = null; }}// functio to insert a node in// tail in circular linked listfunction insertNode(head, tail, d){ // first insertion in circular // linked list if(head == null){ let newNode = new Node(d); head = newNode; tail = newNode; newNode.next = newNode; } else{ // non-empty list let temp = new Node(d); temp.next = tail.next; tail.next = temp; tail = tail.next; } return [head, tail];}// functio to print circular linked listfunction print(head){ let curr = head; // if circular linked list is empty if(head == null){ console.log("List is Empty."); return; } // else iterate until node is not head do{ console.log(curr.data + " "); curr = curr.next; }while(curr != head); console.log("");}function convertString(head){ let curr = head; let s = ""; // if circular linked list is empty if(head == null) return ""; // else iterate until node is not head do{ s += (curr.data).toString(); s += "*"; curr = curr.next; }while(curr != head); return s;}// function to check that two circular// linked list are identical or notfunction checkIdentical(S, T){ // check if sizes of two strings are same if(S.length != T.length) return false; let temp = S+S; if(temp.includes(T)) return true; else return false;}// driver programlet head1 = null;let tail1 = null;[head1, tail1] = insertNode(head1, tail1, 1);[head1, tail1] = insertNode(head1, tail1, 2);[head1, tail1] = insertNode(head1, tail1, 3);[head1, tail1] = insertNode(head1, tail1, 4);[head1, tail1] = insertNode(head1, tail1, 5);[head1, tail1] = insertNode(head1, tail1, 1);[head1, tail1] = insertNode(head1, tail1, 2);[head1, tail1] = insertNode(head1, tail1, 6);let head2 = null;let tail2 = null;[head2, tail2] = insertNode(head2, tail2, 5);[head2, tail2] = insertNode(head2, tail2, 1);[head2, tail2] = insertNode(head2, tail2, 2);[head2, tail2] = insertNode(head2, tail2, 6);[head2, tail2] = insertNode(head2, tail2, 1);[head2, tail2] = insertNode(head2, tail2, 2);[head2, tail2] = insertNode(head2, tail2, 3);[head2, tail2] = insertNode(head2, tail2, 4);console.log("First circular linked list : ");print(head1);console.log("Second circular linked list : ");print(head2);let S = convertString(head1);let T = convertString(head2);let flag = checkIdentical(S, T);if(flag) console.log("Identical");else console.log("Not Identical");// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;// C# program to Check that two circular// linked list are identical or notclass HelloWorld { public class Node { public int data; public Node next; public Node(int d) {data = d; next = null;} } // Function to insert a node in // tail in circular linked list public static List<Node> insertNode(Node head, Node tail, int d) { // First insertion in circular // linked list if (head == null) { Node newNode = new Node(d); head = newNode; tail = newNode; newNode.next = newNode; } else { // Non-empty list Node temp = new Node(d); temp.next = tail.next; tail.next = temp; tail = tail.next; } List<Node> ans = new List<Node>(); ans.Add(head); ans.Add(tail); return ans; } public static string convertString(Node head) { Node curr = head; string s = ""; // If circular linked list is empty if (head == null) { return ""; } // Else iterate until node is NOT head do { s += curr.data.ToString(); s += "*"; curr = curr.next; } while (curr != head); return s; } // Function to print circular linked list public static void print(Node head) { Node curr = head; // If circular linked list is empty if (head == null) { Console.WriteLine("List is Empty "); return; } // Else iterate until node is NOT head do { Console.Write(curr.data + " "); curr = curr.next; } while (curr != head); Console.WriteLine(); } // Function to Check that two circular // linked list are identical or not public static bool checkIdentical(string S, string T) { /* Check if sizes of two strings are same */ if (S.Length != T.Length) return false; string temp = S + S; if(temp.Contains(T)) return true; return false; } static void Main() { Node head1 = null; Node tail1 = null; List<Node> a = insertNode(head1, tail1, 1); head1 = a[0]; tail1 = a[1]; a = insertNode(head1, tail1, 2); head1 = a[0]; tail1 = a[1]; a = insertNode(head1, tail1, 3); head1 = a[0]; tail1 = a[1]; a = insertNode(head1, tail1, 4); head1 = a[0]; tail1 = a[1]; a = insertNode(head1, tail1, 5); head1 = a[0]; tail1 = a[1]; a = insertNode(head1, tail1, 1); head1 = a[0]; tail1 = a[1]; a = insertNode(head1, tail1, 2); head1 = a[0]; tail1 = a[1]; a = insertNode(head1, tail1, 6); head1 = a[0]; tail1 = a[1]; Node head2 = null; Node tail2 = null; a = insertNode(head2, tail2, 5); head2 = a[0]; tail2 = a[1]; a = insertNode(head2, tail2, 1); head2 = a[0]; tail2 = a[1]; a = insertNode(head2, tail2, 2); head2 = a[0]; tail2 = a[1]; a = insertNode(head2, tail2, 6); head2 = a[0]; tail2 = a[1]; a = insertNode(head2, tail2, 1); head2 = a[0]; tail2 = a[1]; a = insertNode(head2, tail2, 2); head2 = a[0]; tail2 = a[1]; a = insertNode(head2, tail2, 3); head2 = a[0]; tail2 = a[1]; a = insertNode(head2, tail2, 4); head2 = a[0]; tail2 = a[1]; Console.Write("First circular linked list: "); print(head1); Console.Write("Second circular linked list: "); print(head2); string S = convertString(head1); string T = convertString(head2); bool flag = checkIdentical(S, T); if (flag) Console.WriteLine("Identical"); else Console.WriteLine("Not Identical"); }}// The code is contributed by Nidhi goel. |
Output
First circular linked list: 1 2 3 4 5 1 2 6 Second circular linked list: 5 1 2 6 1 2 3 4 Identical
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
