Given two linked lists L1 and L2 in which in every node a string is stored. The task is to check whether the strings combining all the nodes are similar or not.
Examples:
Input: L1 = [“He”, “llo”, “wor”, “ld”],
L2 = [“H”, “e”, “ll”, “owo”, “r”, “ld”]
Output: true
Explanation: both lists makes the string of “Helloworld”.Input: L1 = [“w”, “o”, “l”, “d”],
L2 = [“wo”, “d”, “rl”]
Output: false
Explanation: L1 makes “world” but L2 makes “wodrl” both are different.Input: L1 = [“w”, “”, “orl”, “d”],
L2 = [“worl”, “”, “”, “”, “d”]
Output: true
Explanation: both lists makes the string of “world”.
Naive Approach: This is the simple approach. Traverse both the lists and store their values in another string, then compare both strings if equal return true else return false.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Structure of Node of linked listclass Node {public: string s; Node* next; Node(string s) { this->s = s; next = NULL; }};// Function to compare if two linkedlists// are similar or notbool compare(Node* list1, Node* list2){ // Declare string variables to store // the strings formed from the linked lists string s1, s2; while (list1 != NULL) { s1 += list1->s; list1 = list1->next; } while (list2 != NULL) { s2 += list2->s; list2 = list2->next; } return s1 == s2;}// Driver Codeint main(){ Node* n1 = new Node("w"); Node* head1 = n1; Node* n2 = new Node(""); Node* n3 = new Node("orl"); Node* n4 = new Node("d"); Node* n5 = new Node("worl"); Node* head2 = n5; Node* n6 = new Node(""); Node* n7 = new Node(""); Node* n8 = new Node("nd"); n1->next = n2; n2->next = n3; n3->next = n4; n5->next = n6; n6->next = n7; n7->next = n8; if (compare(head1, head2) == true) cout << "true"; else cout << "false"; return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Structure of Node of linked list public static class Node { public String s; public Node next; public Node(String s) { this.s = s; next = null; } }; // Function to compare if two linkedlists // are similar or not public static boolean compare(Node list1, Node list2) { // Declare String variables to store // the Strings formed from the linked lists String s1 = "", s2 = ""; while (list1 != null) { s1 += list1.s; list1 = list1.next; } while (list2 != null) { s2 += list2.s; list2 = list2.next; } return s1.equals(s2); } // Driver Code public static void main(String[] args) { Node n1 = new Node("w"); Node head1 = n1; Node n2 = new Node(""); Node n3 = new Node("orl"); Node n4 = new Node("d"); Node n5 = new Node("worl"); Node head2 = n5; Node n6 = new Node(""); Node n7 = new Node(""); Node n8 = new Node("nd"); n1.next = n2; n2.next = n3; n3.next = n4; n5.next = n6; n6.next = n7; n7.next = n8; if (compare(head1, head2) == true) System.out.println("true"); else System.out.println("false"); }}// this code is contributed by bhardwajji |
Python3
# Python code for the above approach# Structure of Node of linked listclass Node: def __init__(self,str): self.s = str self.next = None# Function to compare if two linkedlists# are similar or notdef compare(list1, list2): # Declare string variables to store # the strings formed from the linked lists s1,s2 = "","" while (list1 != None): s1 += list1.s list1 = list1.next while (list2 != None): s2 += list2.s list2 = list2.next return s1 == s2# Driver Coden1 = Node("w")head1 = n1n2 = Node("")n3 = Node("orl")n4 = Node("d")n5 = Node("worl")head2 = n5n6 = Node("")n7 = Node("")n8 = Node("nd")n1.next = n2n2.next = n3n3.next = n4n5.next = n6n6.next = n7n7.next = n8if (compare(head1, head2) == True): print("true")else: print("false")# This code is contributed by shinjanpatra |
C#
// C# program for above approachusing System;using System.Collections.Generic;class GFG{ // Structure of Node of linked list public class Node { public String s; public Node next; public Node(String s) { this.s = s; next = null; } }; // Function to compare if two linkedlists // are similar or not static bool compare(Node list1, Node list2) { // Declare String variables to store // the Strings formed from the linked lists String s1 ="", s2=""; while (list1 != null) { s1 += list1.s; list1 = list1.next; } while (list2 != null) { s2 += list2.s; list2 = list2.next; } return s1 == s2; } // Driver Code public static void Main() { Node n1 = new Node("w"); Node head1 = n1; Node n2 = new Node(""); Node n3 = new Node("orl"); Node n4 = new Node("d"); Node n5 = new Node("worl"); Node head2 = n5; Node n6 = new Node(""); Node n7 = new Node(""); Node n8 = new Node("nd"); n1.next = n2; n2.next = n3; n3.next = n4; n5.next = n6; n6.next = n7; n7.next = n8; if (compare(head1, head2) == true) Console.Write("true"); else Console.Write("false"); }}// This code is contributed by jana_sayantan. |
Javascript
<script> // JavaScript code for the above approach // Structure of Node of linked list class Node { constructor(str) { this.s = str; this.next = null; } }; // Function to compare if two linkedlists // are similar or not function compare(list1, list2) { // Declare string variables to store // the strings formed from the linked lists let s1 = "", s2 = ""; while (list1 != null) { s1 += list1.s; list1 = list1.next; } while (list2 != null) { s2 += list2.s; list2 = list2.next; } return s1 == s2; } // Driver Code let n1 = new Node("w"); let head1 = n1; let n2 = new Node(""); let n3 = new Node("orl"); let n4 = new Node("d"); let n5 = new Node("worl"); let head2 = n5; let n6 = new Node(""); let n7 = new Node(""); let n8 = new Node("nd"); n1.next = n2; n2.next = n3; n3.next = n4; n5.next = n6; n6.next = n7; n7.next = n8; if (compare(head1, head2) == true) document.write("true"); else document.write("false");// This code is contributed by Potta Lokesh </script> |
Output
false
Time Complexity: O(N+M) where N and M are lengths of the strings.
Auxiliary Space: O(N+M)
Efficient Approach: This problem can be solved by using Two pointers approach. Follow the steps below to solve the given problem.
- Traverse both the lists while maintaining two pointers for the characters.
- Compare each of the characters separately. If different, return false otherwise, continue to compare.
- If the pointer’s value becomes the size of a string in a node, then move to the next node.
- Repeat the steps until the nodes do not become NULL.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Structure of Node of a linked listclass Node {public: string s; Node* next; Node(string s) { this->s = s; next = NULL; }};// Compare functionbool compare(Node* list1, Node* list2){ int i = 0, j = 0; while (list1 != NULL && list2 != NULL) { while (i < list1->s.size() && j < list2->s.size()) { if (list1->s[i] != list2->s[j]) return false; i++; j++; } if (i == list1->s.size()) { i = 0; list1 = list1->next; } if (j == list2->s.size()) { j = 0; list2 = list2->next; } } return list1 == NULL && list2 == NULL;}// Driver Codeint main(){ Node* n1 = new Node("w"); Node* head1 = n1; Node* n2 = new Node(""); Node* n3 = new Node("orl"); Node* n4 = new Node("d"); Node* n5 = new Node("worl"); Node* head2 = n5; Node* n6 = new Node(""); Node* n7 = new Node(""); Node* n8 = new Node("nd"); n1->next = n2; n2->next = n3; n3->next = n4; n5->next = n6; n6->next = n7; n7->next = n8; if (compare(head1, head2) == true) cout << "true"; else cout << "false"; return 0;} |
Java
// Java program for above approachpublic class Compare { // Structure of Node of a linked list static class Node { String s; Node next; Node(String s) { this.s = s; next = null; } } // Compare function static boolean compare(Node list1, Node list2) { int i = 0, j = 0; while (list1 != null && list2 != null) { while (i < list1.s.length() && j < list2.s.length()) { if (list1.s.charAt(i) != list2.s.charAt(j)) return false; i++; j++; } if (i == list1.s.length()) { i = 0; list1 = list1.next; } if (j == list2.s.length()) { j = 0; list2 = list2.next; } } return list1 == null && list2 == null; } // Driver Code public static void main(String[] args) { Node n1 = new Node("w"); Node head1 = n1; Node n2 = new Node(""); Node n3 = new Node("orl"); Node n4 = new Node("d"); Node n5 = new Node("worl"); Node head2 = n5; Node n6 = new Node(""); Node n7 = new Node(""); Node n8 = new Node("nd"); n1.next = n2; n2.next = n3; n3.next = n4; n5.next = n6; n6.next = n7; n7.next = n8; if (compare(head1, head2) == true) System.out.println("true"); else System.out.println("false"); }}// This code is contributed by Lovely Jain |
Python3
# Python program recursively print all sentences that can be# Structure of Node of a linked listclass Node: def __init__(self,s): self.s = s self.next = None# Compare functiondef compare(list1, list2): i,j = 0,0 while (list1 != None and list2 != None): while (i < len(list1.s) and j < len(list2.s)): if (list1.s[i] != list2.s[j]): return False i += 1 j += 1 if (i == len(list1.s)): i = 0 list1 = list1.next if (j == len(list2.s)): j = 0 list2 = list2.next return list1 == None and list2 == None# Driver Coden1 = Node("w")head1 = n1n2 = Node("")n3 = Node("orl")n4 = Node("d")n5 = Node("worl")head2 = n5n6 = Node("")n7 = Node("")n8 = Node("nd")n1.next = n2n2.next = n3n3.next = n4n5.next = n6n6.next = n7n7.next = n8if (compare(head1, head2) == True): print("true")else: print("false")# This code is contributed by shinjanpatra |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Compare function static bool compare(Node list1, Node list2) { int i = 0, j = 0; while (list1 != null && list2 != null) { while (i < list1.s.Length && j < list2.s.Length) { if (list1.s[i] != list2.s[j]) return false; i++; j++; } if (i == list1.s.Length) { i = 0; list1 = list1.next; } if (j == list2.s.Length) { j = 0; list2 = list2.next; } } return list1 == null && list2 == null; } // Driver code public static void Main(string[] args){ Node n1 = new Node("w"); Node head1 = n1; Node n2 = new Node(""); Node n3 = new Node("orl"); Node n4 = new Node("d"); Node n5 = new Node("worl"); Node head2 = n5; Node n6 = new Node(""); Node n7 = new Node(""); Node n8 = new Node("nd"); n1.next = n2; n2.next = n3; n3.next = n4; n5.next = n6; n6.next = n7; n7.next = n8; if (compare(head1, head2) == true) Console.WriteLine("true"); else Console.WriteLine("false"); }}// Structure of Node of a linked listpublic class Node{ public String s; public Node next; public Node(String s) { this.s = s; next = null; }}// This code is contributed by subhamgoyal2014. |
Javascript
<script>// JavaScript program recursively print all sentences that can be// Structure of Node of a linked listclass Node { constructor(s) { this.s = s; this.next = null; }}// Compare functionfunction compare(list1, list2){ let i = 0, j = 0; while (list1 != null && list2 != null) { while (i < list1.s.length && j < list2.s.length) { if (list1.s[i] != list2.s[j]) return false; i++; j++; } if (i == list1.s.length) { i = 0; list1 = list1.next; } if (j == list2.s.length) { j = 0; list2 = list2.next; } } return list1 == null && list2 == null;}// Driver Codelet n1 = new Node("w");let head1 = n1;let n2 = new Node("");let n3 = new Node("orl");let n4 = new Node("d");let n5 = new Node("worl");let head2 = n5;let n6 = new Node("");let n7 = new Node("");let n8 = new Node("nd");n1.next = n2;n2.next = n3;n3.next = n4;n5.next = n6;n6.next = n7;n7.next = n8;if (compare(head1, head2) == true) document.write("true");else document.write("false");// This code is contributed by shinjanpatra</script> |
Output
false
Time Complexity: O(N+M) where N and M are length of the strings.
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!
