Dadas dos listas ordenadas en orden creciente, cree y devuelva una nueva lista que represente la intersección de las dos listas. La nueva lista debe hacerse con su propia memoria; las listas originales no deben cambiarse.
Ejemplo:
Input: First linked list: 1->2->3->4->6 Second linked list be 2->4->6->8, Output: 2->4->6. The elements 2, 4, 6 are common in both the list so they appear in the intersection list. Input: First linked list: 1->2->3->4->5 Second linked list be 2->3->4, Output: 2->3->4 The elements 2, 3, 4 are common in both the list so they appear in the intersection list.
Método : Uso del Node ficticio.
Enfoque:
la idea es utilizar un Node ficticio temporal al comienzo de la lista de resultados. La cola del puntero siempre apunta al último Node en la lista de resultados, por lo que se pueden agregar nuevos Nodes fácilmente. El Node ficticio inicialmente le da a la cola un espacio de memoria al que apuntar. Este Node ficticio es eficiente, ya que solo es temporal y se asigna en la pila. El ciclo continúa, eliminando un Node de ‘a’ o ‘b’ y agregándolo a la cola. Cuando se recorren las listas dadas, el resultado es ficticio. siguiente, ya que los valores se asignan desde el siguiente Node del dummy. Si ambos elementos son iguales, elimine ambos e inserte el elemento en la cola. De lo contrario, elimine el elemento más pequeño entre ambas listas.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program to implement
# the above approach
# Link list node
class Node:
def __init__(self):
self.data = 0
self.next = None
''' This solution uses the temporary
dummy to build up the result list '''
def sortedIntersect(a, b):
dummy = Node()
tail = dummy;
dummy.next = None;
''' Once one or the other
list runs out -- we're done '''
while (a != None and b != None):
if (a.data == b.data):
tail.next = push((tail.next),
a.data);
tail = tail.next;
a = a.next;
b = b.next;
# Advance the smaller list
elif(a.data < b.data):
a = a.next;
else:
b = b.next;
return (dummy.next);
''' UTILITY FUNCTIONS '''
''' Function to insert a node at
the beginning of the linked list '''
def push(head_ref, new_data):
# Allocate node
new_node = Node()
# Put in the data
new_node.data = new_data;
# Link the old list off the new node
new_node.next = (head_ref);
# Move the head to point to the
# new node
(head_ref) = new_node;
return head_ref
''' Function to print nodes in
a given linked list '''
def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next;
# Driver code
if __name__=='__main__':
# Start with the empty lists
a = None;
b = None;
intersect = None;
''' Let us create the first sorted
linked list to test the functions
Created linked list will be
1.2.3.4.5.6 '''
a = push(a, 6);
a = push(a, 5);
a = push(a, 4);
a = push(a, 3);
a = push(a, 2);
a = push(a, 1);
''' Let us create the second sorted
linked list. Created linked list
will be 2.4.6.8 '''
b = push(b, 8);
b = push(b, 6);
b = push(b, 4);
b = push(b, 2);
# Find the intersection two linked lists
intersect = sortedIntersect(a, b);
print("Linked list containing common items of a & b ");
printList(intersect);
# This code is contributed by rutvik_56.
Producción:
Linked list containing common items of a & b 2 4 6
Análisis de Complejidad:
- Complejidad de tiempo: O(m+n) donde m y n son el número de Nodes en la primera y segunda lista enlazada respectivamente.
Solo se necesita un recorrido de las listas. - Espacio Auxiliar: O(min(m, n)).
La lista de salida puede almacenar como máximo min(m,n) Nodes.
¡ Consulte el artículo completo sobre la intersección de dos listas enlazadas ordenadas 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