Programa de Python para comprobar si dos listas enlazadas son idénticas

Dos listas enlazadas son idénticas cuando tienen los mismos datos y la disposición de los datos también es la misma. Por ejemplo, las listas enlazadas a (1->2->3) yb(1->2->3) son idénticas. . Escribe una función para verificar si las dos listas enlazadas dadas son idénticas. 

Método 1 (iterativo): 
para identificar si dos listas son idénticas, debemos recorrer ambas listas simultáneamente y, mientras las recorremos, debemos comparar los datos.

# An iterative Java program to check if 
# two linked lists are identical or not 
  
# Linked list Node 
class Node: 
    def __init__(self, d):
        self.data = d
        self.next = None
  
class LinkedList:
    def __init__(self):
  
        # Head of list 
        self.head = None 
      
    # Returns true if linked lists a 
    # and b are identical, otherwise false 
    def areIdentical(self, listb): 
        a = self.head
        b = listb.head
  
        while (a != None and b != None): 
            if (a.data != b.data): 
                return False
  
            # If we reach here, then a and b 
            # are not null and their data is 
            # same, so move to next nodes 
            # in both lists 
            a = a.next
            b = b.next
  
        # If linked lists are identical, 
        # then 'a' and 'b' must be null
        # at this point. 
        return (a == None and b == None) 
  
    # UTILITY FUNCTIONS TO TEST fun1() 
    # and fun2() 
    # Given a reference (pointer to pointer) 
    # to the head of a list and an int, push 
    # a new node on the front of the list. 
    def push(self, new_data):
          
        # 1 & 2: Allocate the Node & 
        # Put in the data
        new_node = Node(new_data) 
  
        # 3. Make next of new Node as head 
        new_node.next = self.head 
  
        # 4. Move the head to point to 
        # new Node 
        self.head = new_node
  
# Driver Code
llist1 = LinkedList() 
llist2 = LinkedList() 
  
# The constructed linked lists are : 
# llist1: 3->2->1 
# llist2: 3->2->1 
llist1.push(1) 
llist1.push(2) 
llist1.push(3) 
llist2.push(1) 
llist2.push(2) 
llist2.push(3) 
  
if (llist1.areIdentical(llist2) == True): 
    print("Identical ")
else:
    print("Not identical ")
# This code is contributed by Prerna Saini

Producción: 

Identical

Método 2 (recursivo): 
el código de solución recursivo es mucho más limpio que el código iterativo. Sin embargo, probablemente no desee utilizar la versión recursiva para el código de producción, ya que utilizará el espacio de pila que es proporcional a la longitud de las listas.

# A recursive Python3 function to check 
# if two linked lists are identical 
# or not 
def areIdentical(a, b): 
      
    # If both lists are empty 
    if (a == None and b == None): 
        return True
  
    # If both lists are not empty, 
    # then data of current nodes must 
    # match, and same should be recursively 
    # true for rest of the nodes. 
    if (a != None and b != None): 
        return ((a.data == b.data) and 
                 areIdentical(a.next, b.next)) 
  
    # If we reach here, then one of the lists 
    # is empty and other is not 
    return False
# This code is contributed by Princi Singh

Complejidad de tiempo: O(n) para versiones iterativas y recursivas. n es la longitud de la lista más pequeña entre a y b.

Consulte el artículo completo sobre listas vinculadas idénticas para obtener más detalles.