Programa C para encontrar el punto de intersección de dos listas vinculadas

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:

// C program to get intersection point
//  of two linked list
#include <stdio.h>
#include <stdlib.h>
  
// Link list node 
struct Node 
{
    int data;
    struct Node* next;
};
  
// Function to get the counts of node 
// in a linked list 
int getCount(struct 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, struct Node* head1, 
                        struct Node* head2);
  
/* function to get the intersection point
   of two linked lists head1 and head2 */
int getIntesectionNode(struct Node* head1, 
                       struct Node* head2)
{
    int c1 = getCount(head1);
    int c2 = getCount(head2);
    int d;
  
    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, struct Node* head1, 
                        struct Node* head2)
{
    int i;
    struct Node* current1 = head1;
    struct Node* current2 = head2;
  
    for (i = 0; i < d; i++)
    {
        if (current1 == NULL) 
        {
            return -1;
        }
        current1 = current1->next;
    }
  
    while (current1 != NULL && 
           current2 != NULL) 
    {
        if (current1 == current2)
            return current1->data;
        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(struct Node* head)
{
    struct Node* current = head;
    int count = 0;
  
    while (current != NULL) 
    {
        count++;
        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 */
    struct Node* newNode;
    struct Node* head1 = 
           (struct Node*)malloc(sizeof(struct Node));
    head1->data = 10;
  
    struct Node* head2 = 
           (struct Node*)malloc(sizeof(struct Node));
    head2->data = 3;
  
    newNode = 
    (struct Node*)malloc(sizeof(struct Node));
    newNode->data = 6;
    head2->next = newNode;
  
    newNode = 
    (struct Node*)malloc(sizeof(struct Node));
    newNode->data = 9;
    head2->next->next = newNode;
  
    newNode = 
    (struct Node*)malloc(sizeof(struct Node));
    newNode->data = 15;
    head1->next = newNode;
    head2->next->next->next = newNode;
  
    newNode = 
    (struct Node*)malloc(sizeof(struct Node));
    newNode->data = 30;
    head1->next->next = newNode;
  
    head1->next->next->next = NULL;
  
    printf("The node of intersection is %d ",
            getIntesectionNode(head1, head2));
  
    getchar();
}

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 the 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)

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.