Hay dos listas enlazadas individualmente en un sistema. Por algún error de programación, el Node final de una de las listas vinculadas se vinculó a la segunda lista, formando una lista en forma de Y invertida. Escriba un programa para obtener el punto donde se fusionan dos listas enlazadas.
El diagrama anterior muestra un ejemplo con dos listas vinculadas que tienen 15 como puntos de intersección.
Método 1 (simplemente use dos bucles):
use 2 anidados para bucles. El ciclo externo será para cada Node de la primera lista y el ciclo interno será para la segunda lista. En el bucle interno, verifique si alguno de los Nodes de la segunda lista es el mismo que el Node actual de la primera lista vinculada. La complejidad temporal de este método será O(M * N) donde m y n son los números de Nodes en dos listas.
Método 2 (Marcar Nodes visitados):
esta solución requiere modificaciones en la estructura básica de datos de la lista vinculada. Tenga una bandera visitada con cada Node. Recorra la primera lista enlazada y siga marcando los Nodes visitados. Ahora recorra la segunda lista enlazada. Si vuelve a ver un Node visitado, entonces hay un punto de intersección, devuelva el Node de intersección. Esta solución funciona en O(m+n) pero requiere información adicional con cada Node. Se puede implementar una variación de esta solución que no requiere modificar la estructura de datos básica mediante un hash. Recorra la primera lista enlazada y almacene las direcciones de los Nodes visitados en un hash. Ahora recorra la segunda lista enlazada y si ve una dirección que ya existe en el hash, devuelva el Node de intersección.
Método 3 (usando la diferencia de recuentos de Nodes):
- Obtenga la cuenta de los Nodes en la primera lista, deje que la cuenta sea c1.
- Obtenga la cuenta de los Nodes en la segunda lista, deje que la cuenta sea c2.
- Obtener la diferencia de conteos d = abs(c1 – c2)
- Ahora recorra la lista más grande desde el primer Node hasta d Nodes para que de aquí en adelante ambas listas tengan el mismo número de Nodes
- Entonces podemos recorrer ambas listas en paralelo hasta que encontremos un Node común. (Tenga en cuenta que obtener un Node común se realiza comparando la dirección de los Nodes)
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to get intersection point of two linked list
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node* next;
};
// Function to get the counts of
// node in a linked list
int getCount(Node* head);
/* Function to get the intersection
point of two linked lists head1
and head2 where head1 has d more
nodes than head2 */
int _getIntesectionNode(int d, Node* head1,
Node* head2);
/* Function to get the intersection point
of two linked lists head1 and head2 */
int getIntesectionNode(Node* head1,
Node* head2)
{
// Count the number of nodes in
// both the linked list
int c1 = getCount(head1);
int c2 = getCount(head2);
int d;
// If first is greater
if (c1 > c2)
{
d = c1 - c2;
return _getIntesectionNode(d, head1,
head2);
}
else
{
d = c2 - c1;
return _getIntesectionNode(d, head2,
head1);
}
}
/* Function to get the intersection point
of two linked lists head1 and head2
where head1 has d more nodes than head2 */
int _getIntesectionNode(int d, Node* head1,
Node* head2)
{
// Stand at the starting of the
// bigger list
Node* current1 = head1;
Node* current2 = head2;
// Move the pointer forward
for (int i = 0; i < d; i++)
{
if (current1 == NULL)
{
return -1;
}
current1 = current1->next;
}
// Move both pointers of both list till
// they intersect with each other
while (current1 != NULL &&
current2 != NULL)
{
if (current1 == current2)
return current1->data;
// Move both the pointers forward
current1 = current1->next;
current2 = current2->next;
}
return -1;
}
/* Takes head pointer of the linked list and
returns the count of nodes in the list */
int getCount(Node* head)
{
Node* current = head;
// Counter to store count of nodes
int count = 0;
// Iterate till NULL
while (current != NULL)
{
// Increase the counter
count++;
// Move the Node ahead
current = current->next;
}
return count;
}
// Driver Code
int main()
{
/* Create two linked lists
1st 3->6->9->15->30
2nd 10->15->30
15 is the intersection point */
Node* newNode;
// Addition of new nodes
Node* head1 = new Node();
head1->data = 10;
Node* head2 = new Node();
head2->data = 3;
newNode = new Node();
newNode->data = 6;
head2->next = newNode;
newNode = new Node();
newNode->data = 9;
head2->next->next = newNode;
newNode = new Node();
newNode->data = 15;
head1->next = newNode;
head2->next->next->next = newNode;
newNode = new Node();
newNode->data = 30;
head1->next->next = newNode;
head1->next->next->next = NULL;
cout << "The node of intersection is " <<
getIntesectionNode(head1, head2);
}
// This code is contributed by rathbhupendra
Producción:
The node of intersection is 15
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA