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 bucle exterior será para cada Node de la primera lista y el bucle interior 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:
Javascript
<script>
// Javascript program to implement
// the above approach
class Node
{
constructor(item)
{
this.data=item;
this.next=null;
}
}
let head1,head2;
function getNode()
{
let c1 = getCount(head1);
let c2 = getCount(head2);
let d;
if (c1 > c2)
{
d = c1 - c2;
return _getIntesectionNode(d, head1,
head2);
}
else
{
d = c2 - c1;
return _getIntesectionNode(d, head2,
head1);
}
}
function _getIntesectionNode(d, node1,
node2)
{
let i;
let current1 = node1;
let current2 = node2;
for (i = 0; i < d; i++)
{
if (current1 == null)
{
return -1;
}
current1 = current1.next;
}
while (current1 != null &&
current2 != null)
{
if (current1.data == current2.data)
{
return current1.data;
}
current1 = current1.next;
current2 = current2.next;
}
return -1;
}
function getCount(node)
{
let current = node;
let count = 0;
while (current != null)
{
count++;
current = current.next;
}
return count;
}
head1 = new Node(3);
head1.next = new Node(6);
head1.next.next = new Node(9);
head1.next.next.next = new Node(15);
head1.next.next.next.next = new Node(30);
// Creating second linked list
head2 = new Node(10);
head2.next = new Node(15);
head2.next.next = new Node(30);
document.write("The node of intersection is " +
getNode());
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
The node of intersection is 15
Complejidad temporal: O(m+n)
Espacio auxiliar: O(1)
Método 4 (haga un círculo en la primera lista):
gracias a Saravanan Man por proporcionar la solución a continuación.
1. Recorra la primera lista enlazada (cuente los elementos) y haga una lista enlazada circular. (Recuerde el último Node para que podamos romper el círculo más adelante).
2. Ahora vea el problema como encontrar el bucle en la segunda lista enlazada. Así que el problema está resuelto.
3. Como ya conocemos la longitud del bucle (tamaño de la primera lista enlazada), podemos recorrer esa cantidad de Nodes en la segunda lista y luego iniciar otro puntero desde el principio de la segunda lista. tenemos que atravesar hasta que sean iguales, y ese es el punto de intersección requerido.
4. elimine el círculo de la lista vinculada.
Complejidad temporal: O(m+n)
Espacio auxiliar: O(1)
Método 5 (Invertir la primera lista y hacer ecuaciones):
Gracias a Saravanan Mani por proporcionar este método.
1) Let X be the length of the first linked list until intersection point.
Let Y be the length of the second linked list until the intersection point.
Let Z be the length of the linked list from the intersection point to End of
the linked list including the intersection node.
We Have
X + Z = C1;
Y + Z = C2;
2) Reverse first linked list.
3) Traverse Second linked list. Let C3 be the length of second list - 1.
Now we have
X + Y = C3
We have 3 linear equations. By solving them, we get
X = (C1 + C3 – C2)/2;
Y = (C2 + C3 – C1)/2;
Z = (C1 + C2 – C3)/2;
WE GOT THE INTERSECTION POINT.
4) Reverse first linked list.
Ventaja: No hay comparación de punteros.
Desventaja: modificación de la lista enlazada (lista de inversión).
Complejidad temporal: O(m+n)
Espacio auxiliar: O(1)
Método 6 (Recorre ambas listas y compara las direcciones de los últimos Nodes): Este método es solo para detectar si hay un punto de intersección o no. (Gracias a NeoTheSaviour por sugerir esto)
1) Traverse list 1, store the last node address 2) Traverse list 2, store the last node address. 3) If nodes stored in 1 and 2 are same then they are intersecting.
La complejidad temporal de este método es O(m+n) y el espacio auxiliar utilizado es O(1)
Método 7 (Usar Hashing):
Básicamente, necesitamos encontrar un Node común de dos listas enlazadas. Así que hacemos hash de todos los Nodes de la primera lista y luego verificamos la segunda lista.
1) Cree un conjunto hash vacío.
2) Atraviese la primera lista enlazada e inserte las direcciones de todos los Nodes en el conjunto hash.
3) Recorrer la segunda lista. Para cada Node, compruebe si está presente en el conjunto hash. Si encontramos un Node en el conjunto hash, devolvemos el Node.
Javascript
<script>
// Javascript program to get intersection
// point of two linked list
class Node
{
constructor(d)
{
this.data = d;
this.next = null;
}
}
// Function to print the list
function Print(n)
{
let cur = n;
while (cur != null)
{
document.write(cur.data + " ");
cur = cur.next;
}
document.write("<br>");
}
// Function to find the intersection
// of two node
function MegeNode(n1, n2)
{
// Define hashset
let hs = new Set();
while (n1 != null)
{
hs.add(n1);
n1 = n1.next;
}
while (n2 != null)
{
if (hs.has(n2))
{
return n2;
}
n2 = n2.next;
}
return null;
}
// Driver code
// List 1
let n1 = new Node(1);
n1.next = new Node(2);
n1.next.next = new Node(3);
n1.next.next.next = new Node(4);
n1.next.next.next.next = new Node(5);
n1.next.next.next.next.next = new Node(6);
n1.next.next.next.next.next.next = new Node(7);
// List 2
let n2 = new Node(10);
n2.next = new Node(9);
n2.next.next = new Node(8);
n2.next.next.next = n1.next.next.next;
Print(n1);
Print(n2);
document.write(MegeNode(n1, n2).data);
// This code is contributed by rag2127
</script>
Producción:
1 2 3 4 5 6 7 10 9 8 4 5 6 7 4
Este método requería O(n) espacio adicional y no era muy eficiente si una lista era grande.
Complejidad temporal: O(m+n) donde m es el tamaño de la lista enlazada 1 y n es el tamaño de la lista enlazada 2
Consulte el artículo completo sobre Escribir una función para obtener el punto de intersección de dos listas vinculadas para obtener más detalles.
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