Dadas dos listas vinculadas, la tarea es verificar si la primera lista está presente en la segunda lista o no.
Ejemplos:
Input : list1 = 10->20
list2 = 5->10->20
Output : LIST FOUND
Input : list1 = 1->2->3->4
list2 = 1->2->1->2->3->4
Output : LIST FOUND
Input : list1 = 1->2->3->4
list2 = 1->2->2->1->2->3
Output : LIST NOT FOUND
Algoritmo:
- Tome el primer Node de la segunda lista.
- Comience a hacer coincidir la primera lista de este primer Node.
- Si todas las listas coinciden, devuelve verdadero.
- De lo contrario, rompa y lleve la primera lista al primer Node nuevamente.
- Y lleva la segunda lista a su segundo Node.
- Repita estos pasos hasta que cualquiera de las listas vinculadas quede vacía.
- Si la primera lista se vuelve vacía, la lista no se encuentra.
A continuación se muestra la implementación.
C++
// C++ program to find a list in second list
#include <bits/stdc++.h>
using namespace std;
// A Linked List node
struct Node
{
int data;
Node* next;
};
// Returns true if first list is present in second
// list
bool findList(Node* first, Node* second)
{
Node* ptr1 = first, *ptr2 = second;
// If both linked lists are empty, return true
if (first == NULL && second == NULL)
return true;
// Else If one is empty and other is not return
// false
if ( first == NULL ||
(first != NULL && second == NULL))
return false;
// Traverse the second list by picking nodes
// one by one
while (second != NULL)
{
// Initialize ptr2 with current node of second
ptr2 = second;
// Start matching first list with second list
while (ptr1 != NULL)
{
// If second list becomes empty and first
// not then return false
if (ptr2 == NULL)
return false;
// If data part is same, go to next
// of both lists
else if (ptr1->data == ptr2->data)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
// If not equal then break the loop
else break;
}
// Return true if first list gets traversed
// completely that means it is matched.
if (ptr1 == NULL)
return true;
// Initialize ptr1 with first again
ptr1 = first;
// And go to next node of second list
second = second->next;
}
return false;
}
/* Function to print nodes in a given linked list */
void printList(Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// Function to add new node to linked lists
Node *newNode(int key)
{
Node *temp = new Node;
temp-> data= key;
temp->next = NULL;
return temp;
}
/* Driver program to test above functions*/
int main()
{
/* Let us create two linked lists to test
the above functions. Created lists shall be
a: 1->2->3->4
b: 1->2->1->2->3->4*/
Node *a = newNode(1);
a->next = newNode(2);
a->next->next = newNode(3);
a->next->next->next = newNode(4);
Node *b = newNode(1);
b->next = newNode(2);
b->next->next = newNode(1);
b->next->next->next = newNode(2);
b->next->next->next->next = newNode(3);
b->next->next->next->next->next = newNode(4);
findList(a,b) ? cout << "LIST FOUND" :
cout << "LIST NOT FOUND";
return 0;
}
Java
// Java program to find a list in second list
import java.util.*;
class GFG
{
// A Linked List node
static class Node
{
int data;
Node next;
};
// Returns true if first list is
// present in second list
static boolean findList(Node first,
Node second)
{
Node ptr1 = first, ptr2 = second;
// If both linked lists are empty,
// return true
if (first == null && second == null)
return true;
// Else If one is empty and
// other is not, return false
if (first == null ||
(first != null && second == null))
return false;
// Traverse the second list by
// picking nodes one by one
while (second != null)
{
// Initialize ptr2 with
// current node of second
ptr2 = second;
// Start matching first list
// with second list
while (ptr1 != null)
{
// If second list becomes empty and
// first not then return false
if (ptr2 == null)
return false;
// If data part is same, go to next
// of both lists
else if (ptr1.data == ptr2.data)
{
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// If not equal then break the loop
else break;
}
// Return true if first list gets traversed
// completely that means it is matched.
if (ptr1 == null)
return true;
// Initialize ptr1 with first again
ptr1 = first;
// And go to next node of second list
second = second.next;
}
return false;
}
/* Function to print nodes in a given linked list */
static void printList(Node node)
{
while (node != null)
{
System.out.printf("%d ", node.data);
node = node.next;
}
}
// Function to add new node to linked lists
static Node newNode(int key)
{
Node temp = new Node();
temp.data= key;
temp.next = null;
return temp;
}
// Driver Code
public static void main(String[] args)
{
/* Let us create two linked lists to test
the above functions. Created lists shall be
a: 1->2->3->4
b: 1->2->1->2->3->4*/
Node a = newNode(1);
a.next = newNode(2);
a.next.next = newNode(3);
a.next.next.next = newNode(4);
Node b = newNode(1);
b.next = newNode(2);
b.next.next = newNode(1);
b.next.next.next = newNode(2);
b.next.next.next.next = newNode(3);
b.next.next.next.next.next = newNode(4);
if(findList(a, b) == true)
System.out.println("LIST FOUND");
else
System.out.println("LIST NOT FOUND");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find a list in second list
class Node:
def __init__(self, value = 0):
self.value = value
self.next = None
# Returns true if first list is
# present in second list
def findList(first, second):
# If both linked lists are empty/None,
# return True
if not first and not second:
return True
# If ONLY one of them is empty,
# return False
if not first or not second:
return False
ptr1 = first
ptr2 = second
# Traverse the second LL by
# picking nodes one by one
while ptr2:
# Initialize 'ptr2' with current
# node of 'second'
ptr2 = second
# Start matching first LL
# with second LL
while ptr1:
# If second LL become empty and
# first not, return False,
# since first LL has not been
# traversed completely
if not ptr2:
return False
# If value of both nodes from both
# LLs are equal, increment pointers
# for both LLs so that next value
# can be matched
else if ptr1.value == ptr2.value:
ptr1 = ptr1.next
ptr2 = ptr2.next
# If a single mismatch is found
# OR ptr1 is None/empty,break out
# of the while loop and do some checks
else:
break
# check 1 :
# If 'ptr1' is None/empty,that means
# the 'first LL' has been completely
# traversed and matched so return True
if not ptr1:
return True
# If check 1 fails, that means, some
# items for 'first' LL are still yet
# to be matched, so start again by
# bringing back the 'ptr1' to point
# to 1st node of 'first' LL
ptr1 = first
# And increment second node element to next
second = second.next
return False
# Driver Code
# Let us create two linked lists to
# test the above functions.
# Created lists would be be
# node_a: 1->2->3->4
# node_b: 1->2->1->2->3->4
node_a = Node(1)
node_a.next = Node(2)
node_a.next.next = Node(3)
node_a.next.next.next = Node(4)
node_b = Node(1)
node_b.next = Node(2)
node_b.next.next = Node(1)
node_b.next.next.next = Node(2)
node_b.next.next.next.next = Node(3)
node_b.next.next.next.next.next = Node(4)
if findList(node_a, node_b):
print("LIST FOUND")
else:
print("LIST NOT FOUND")
# This code is contributed by GauriShankarBadola
C#
// C# program to find a list in second list
using System;
class GFG
{
// A Linked List node
class Node
{
public int data;
public Node next;
};
// Returns true if first list is
// present in second list
static Boolean findList(Node first,
Node second)
{
Node ptr1 = first, ptr2 = second;
// If both linked lists are empty,
// return true
if (first == null && second == null)
return true;
// Else If one is empty and
// other is not, return false
if (first == null ||
(first != null && second == null))
return false;
// Traverse the second list by
// picking nodes one by one
while (second != null)
{
// Initialize ptr2 with
// current node of second
ptr2 = second;
// Start matching first list
// with second list
while (ptr1 != null)
{
// If second list becomes empty and
// first not then return false
if (ptr2 == null)
return false;
// If data part is same, go to next
// of both lists
else if (ptr1.data == ptr2.data)
{
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// If not equal then break the loop
else break;
}
// Return true if first list gets traversed
// completely that means it is matched.
if (ptr1 == null)
return true;
// Initialize ptr1 with first again
ptr1 = first;
// And go to next node of second list
second = second.next;
}
return false;
}
/* Function to print nodes
in a given linked list */
static void printList(Node node)
{
while (node != null)
{
Console.Write("{0} ", node.data);
node = node.next;
}
}
// Function to add new node to linked lists
static Node newNode(int key)
{
Node temp = new Node();
temp.data= key;
temp.next = null;
return temp;
}
// Driver Code
public static void Main(String[] args)
{
/* Let us create two linked lists to test
the above functions. Created lists shall be
a: 1->2->3->4
b: 1->2->1->2->3->4*/
Node a = newNode(1);
a.next = newNode(2);
a.next.next = newNode(3);
a.next.next.next = newNode(4);
Node b = newNode(1);
b.next = newNode(2);
b.next.next = newNode(1);
b.next.next.next = newNode(2);
b.next.next.next.next = newNode(3);
b.next.next.next.next.next = newNode(4);
if(findList(a, b) == true)
Console.Write("LIST FOUND");
else
Console.Write("LIST NOT FOUND");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find a
// list in second list
// A Linked List node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Returns true if first list is
// present in second list
function findList(first, second) {
var ptr1 = first, ptr2 = second;
// If both linked lists are empty,
// return true
if (first == null && second == null)
return true;
// Else If one is empty and
// other is not, return false
if (first == null || (first != null &&
second == null))
return false;
// Traverse the second list by
// picking nodes one by one
while (second != null) {
// Initialize ptr2 with
// current node of second
ptr2 = second;
// Start matching first list
// with second list
while (ptr1 != null) {
// If second list becomes empty and
// first not then return false
if (ptr2 == null)
return false;
// If data part is same, go to next
// of both lists
else if (ptr1.data == ptr2.data) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// If not equal then break the loop
else
break;
}
// Return true if first list gets traversed
// completely that means it is matched.
if (ptr1 == null)
return true;
// Initialize ptr1 with first again
ptr1 = first;
// And go to next node of second list
second = second.next;
}
return false;
}
/* Function to print nodes in a given linked list */
function printList(node) {
while (node != null) {
document.write("%d ", node.data);
node = node.next;
}
}
// Function to add new node to linked lists
function newNode(key) {
var temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// Driver Code
/*
Let us create two linked lists to test
the above functions. Created lists
shall be a: 1->2->3->4 b: 1->2->1->2->3->4
*/
var a = newNode(1);
a.next = newNode(2);
a.next.next = newNode(3);
a.next.next.next = newNode(4);
var b = newNode(1);
b.next = newNode(2);
b.next.next = newNode(1);
b.next.next.next = newNode(2);
b.next.next.next.next = newNode(3);
b.next.next.next.next.next = newNode(4);
if (findList(a, b) == true)
document.write("LIST FOUND");
else
document.write("LIST NOT FOUND");
// This code contributed by gauravrajput1
</script>
Producción
LIST FOUND
Complejidad de tiempo: O(m*n) donde m es el número de Nodes en la segunda lista yn en la primera.
Optimización :
El código anterior se puede optimizar utilizando espacio adicional, es decir, almacena la lista en dos strings y aplica el algoritmo KMP . Consulte https://ide.geeksforgeeks.org/3fXUaV para la implementación proporcionada por Nishant Singh
Echa un vistazo al curso de autoaprendizaje de DSA
Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA