Programa Java para encontrar la intersección de dos listas enlazadas ordenadas

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 1 : 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:

// Java program to implement
// the above approach
class GFG 
{  
    // Head nodes for pointing to 
    // 1st and 2nd linked lists
    static Node a = null, b = null;
    
    // Dummy node for storing 
    // intersection
    static Node dummy = null;
    
    // Tail node for keeping track of 
    // last node so that it makes easy 
    // for insertion
    static Node tail = null;
      
    // class - Node
    static class Node 
    {
        int data;
        Node next;
  
        Node(int data) 
        {
            this.data = data;
            next = null;
        }
    }
      
    // Function for printing the list
    void printList(Node start) 
    {
        Node p = start;
        while (p != null) 
        {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }
      
    // Inserting elements into list
    void push(int data) 
    {
        Node 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 
    void sortedIntersect()
    {      
        // Pointers for iterating
        Node 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
    public static void main(String args[])
    {
        GFG list = new GFG();
          
        // Creating first linked list
        list.a = new Node(1);
        list.a.next = new Node(2);
        list.a.next.next = new Node(3);
        list.a.next.next.next = new Node(4);
        list.a.next.next.next.next = new Node(6);
  
        // Creating second linked list
        list.b = new Node(2);
        list.b.next = new Node(4);
        list.b.next.next = new Node(6);
        list.b.next.next.next = new Node(8);
          
        // Function call for intersection
        list.sortedIntersect();
        
        // Print required intersection
        System.out.println(
               "Linked list containing common items of a & b");
        list.printList(dummy);
    }
}
// This code is contributed by Likhita AVL

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.

Método 2: usar hashing

// Java program to implement
// the above approach
import java.util.*;
  
public class LinkedList 
{
    Node head;
    static class Node 
    {
        int data;
        Node next;            
              
        Node(int d)  
        { 
            data = d;  
            next=null;                 
     }
}
public void printList() 
{
    Node n = head;
    while(n != null) 
    {
        System.out.println(n.data + " ");
        n = n.next;
    }
}
       
public void append(int d) 
{
    Node n = new Node(d);
    if(head== null) 
    {
        head = new Node(d);
        return;
    }
              
    n.next = null;
    Node last = head;
    while(last.next !=null) 
    {
        last = last.next;
    }
    last.next = n;
    return;            
}
          
static int[] intersection(Node tmp1, 
                          Node tmp2, int k) 
{
    int[] res = new int[k];
    HashSet<Integer> set = new HashSet<Integer>();
    while(tmp1 != null) 
    {                
        set.add(tmp1.data);
        tmp1 = tmp1.next;
    }
              
    int cnt = 0;
              
    while(tmp2 != null) 
    {
        if(set.contains(tmp2.data)) 
        {
            res[cnt] = tmp2.data;
            cnt++;
        }
        tmp2 = tmp2.next;
    }
    return res;
              
}
       
// Driver code     
public static void main(String[] args) 
{
    LinkedList ll = new LinkedList();
    LinkedList ll1 = new LinkedList();
           
    ll.append(0);
    ll.append(1);
    ll.append(2);
    ll.append(3);
    ll.append(4);
    ll.append(5);
    ll.append(6);
    ll.append(7);         
           
    ll1.append(9);
    ll1.append(0);
    ll1.append(12);
    ll1.append(3);
    ll1.append(4);
    ll1.append(5);
    ll1.append(6);
    ll1.append(7);
    int[] arr= intersection(ll.head, 
                            ll1.head,6);
    for(int i : arr) 
    {
        System.out.println(i);
    }     
}
// This code is contributed by ayyuce demirbas

Producción:

0
3
4
5
6
7

Análisis de Complejidad:

• Complejidad de tiempo: O(n)

¡ Consulte el artículo completo sobre la intersección de dos listas enlazadas ordenadas para obtener más detalles!