Programa de Python 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:

# Python program to implement
# the above approach
# Defining a node for LinkedList
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None 
  
def getIntersectionNode(head1, head2):
    
    # Finding the total number of elements 
    # in head1 LinkedList
    c1=getCount(head1)
    
    # Finding the total number of elements 
    # in head2 LinkedList
    c2=getCount(head2)
    
    # Traverse the bigger node by 'd' so that
    # from that node onwards, both LinkedList
    # would be having same number of nodes and 
    # we can traverse them together.
    if c1 > c2:
        d = c1 - c2
        return _getIntersectionNode(d, head1,
                                    head2)
    else:
        d = c2 - c1
        return _getIntersectionNode(d, head2,
                                    head1) 
    
  def _getIntersectionNode(d, head1, head2):     
    current1 = head1
    current2 = head2   
  
    for i in range(d):
        if current1 is None:
            return -1
        current1 = current1.next
      
    while current1 is not None and current2 is not None:
      
    # Instead of values, we need to check 
    # if there addresses are same because 
    # there can be a case where value is 
    # same but that value is not an 
    # intersecting point.
        if current1 is current2:
  
            # or current2.data (the value 
            # would be same)
            return current1.data 
      
        current1 = current1.next
        current2 = current2.next
    
    # Incase, we are not able to find 
    # our intersecting point.
    return -1
    
# Function to get the count of a LinkedList
def getCount(node):
    cur=node
    count=0
    while cur is not None:
        count+=1
        cur=cur.next
    return count
      
# Driver code
if __name__ == '__main__':
  
  # Creating two LinkedList
  # 1st one: 3->6->9->15->30
  # 2nd one: 10->15->30
  # We can see that 15 would be 
  # our intersection point
    
  # Defining the common node  
  common = Node(15)
    
  #Defining the first LinkedList  
  head1 = Node(3)
  head1.next = Node(6)
  head1.next.next = Node(9)
  head1.next.next.next = common
  head1.next.next.next.next = Node(30)
    
  # Defining the second LinkedList  
  head2 = Node(10)
  head2.next = common
  head2.next.next = Node(30)
    
  print("The node of intersection is ",
         getIntersectionNode(head1,head2))
# This code is contributed by Ansh Gupta.

Producción:

The node of intersection is 15

Complejidad temporal: O(m+n) 
Espacio auxiliar: O(1)

Método 4 (hacer 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 comienzo 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)

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.