Dadas dos listas enlazadas L1 y L2 en las que en cada Node se almacena una string. La tarea es verificar si las strings que combinan todos los Nodes son similares o no.
Ejemplos:
Entrada: L1 = [“He”, “llo”, “wor”, “ld”],
L2 = [“H”, “e”, “ll”, “owo”, “r”, “ld”]
Salida : verdadero
Explicación: ambas listas forman la string de «Helloworld».Entrada: L1 = [“w”, “o”, “l”, “d”],
L2 = [“wo”, “d”, “rl”]
Salida: falso
Explicación: L1 hace “mundo” pero L2 hace «wodrl» ambos son diferentes.Entrada: L1 = [“w”, “”, “orl”, “d”],
L2 = [“world”, “”, “”, “”, “d”]
Salida: verdadero
Explicación: ambas listas forman el string de «mundo».
Enfoque ingenuo: Este es el enfoque simple. Recorra ambas listas y almacene sus valores en otra string, luego compare ambas strings, si son iguales, devuelven verdadero; de lo contrario, devuelven falso.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Node of linked list
class Node {
public:
string s;
Node* next;
Node(string s)
{
this->s = s;
next = NULL;
}
};
// Function to compare if two linkedlists
// are similar or not
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
int 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 approach
import java.util.*;
class GFG{
// Structure of Node of linked list
static class Node {
String s;
Node next;
Node(String s)
{
this.s = s;
next = null;
}
};
// Function to compare if two linkedlists
// are similar or not
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 == 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.print("true");
else
System.out.print("false");
}
}
// This code is contributed by umadevi9616
Python3
# Python code for the above approach
# Structure of Node of linked list
class Node:
def __init__(self,str):
self.s = str
self.next = None
# Function to compare if two linkedlists
# are similar or not
def 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 Code
n1 = Node("w")
head1 = n1
n2 = Node("")
n3 = Node("orl")
n4 = Node("d")
n5 = Node("worl")
head2 = n5
n6 = Node("")
n7 = Node("")
n8 = 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):
print("true")
else:
print("false")
# This code is contributed by shinjanpatra
C#
// C# program for above approach
using 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>
Producción
false
Complejidad de tiempo: O(N+M) donde N y M son longitudes de las strings.
Espacio Auxiliar: O(N+M)
Enfoque eficiente: este problema se puede resolver utilizando el enfoque de dos punteros . Siga los pasos a continuación para resolver el problema dado.
- Recorra ambas listas mientras mantiene dos punteros para los caracteres.
- Compara cada uno de los personajes por separado. Si es diferente, devuelva falso ; de lo contrario, continúe comparando.
- Si el valor del puntero se convierte en el tamaño de una string en un Node, pase al siguiente Node.
- Repita los pasos hasta que los Nodes no se conviertan en NULL .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Node of a linked list
class Node {
public:
string s;
Node* next;
Node(string s)
{
this->s = s;
next = NULL;
}
};
// Compare function
bool 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 Code
int 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 approach
public 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 list
class Node:
def __init__(self,s):
self.s = s
self.next = None
# Compare function
def 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 Code
n1 = Node("w")
head1 = n1
n2 = Node("")
n3 = Node("orl")
n4 = Node("d")
n5 = Node("worl")
head2 = n5
n6 = Node("")
n7 = Node("")
n8 = 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):
print("true")
else:
print("false")
# This code is contributed by shinjanpatra
C#
// C# program to implement above approach
using 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 list
public 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 list
class Node {
constructor(s)
{
this.s = s;
this.next = null;
}
}
// Compare function
function 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 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 shinjanpatra
</script>
Producción
false
Complejidad de tiempo: O(N+M) donde N y M son la longitud de las strings.
Espacio Auxiliar : O(1).