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:
Javascript
// Javascript program to implement
// the above approach
<script>
// Head nodes for pointing to
// 1st and 2nd linked lists
var a = null, b = null;
// Dummy node for storing intersection
var dummy = null;
// Tail node for keeping track of
// last node so that it makes easy
// for insertion
var tail = null;
// class - Node
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
// Function for printing the list
function printList(start)
{
var p = start;
while (p != null)
{
document.write(p.data + " ");
p = p.next;
}
document.write();
}
// Inserting elements into list
function push(data)
{
var temp = new Node(data);
if (dummy == null)
{
dummy = temp;
tail = temp;
}
else
{
tail.next = temp;
tail = temp;
}
}
// Function for finding intersection
// and adding it to dummy list
function sortedIntersect()
{
// pointers for iterating
var p = a, q = b;
while (p != null && q != null)
{
if (p.data == q.data)
{
// Add to dummy list
push(p.data);
p = p.next;
q = q.next;
}
else if (p.data < q.data)
p = p.next;
else
q = q.next;
}
}
// Driver code
// Creating first linked list
a = new Node(1);
a.next = new Node(2);
a.next.next = new Node(3);
a.next.next.next = new Node(4);
a.next.next.next.next = new Node(6);
// Creating second linked list
b = new Node(2);
b.next = new Node(4);
b.next.next = new Node(6);
b.next.next.next = new Node(8);
// Function call for intersection
sortedIntersect();
// Print required intersection
document.write(
"Linked list containing common items of a & b<br/>");
printList(dummy);
// This code is contributed by todaysgaurav
</script>
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