Combinar dos listas enlazadas ordenadas sin duplicados

Combinar dos listas ordenadas enlazadas de tamaño n1 y n2 . Los duplicados en dos listas enlazadas deben estar presentes solo una vez en la lista enlazada ordenada final.

Ejemplos:  

Input : list1: 1->1->4->5->7
        list2: 2->4->7->9
Output : 1 2 4 5 7 9

Fuente: Microsoft on Campus Colocación y preguntas de la entrevista

Enfoque: Los siguientes son los pasos: 

1. Combine las dos listas enlazadas ordenadas de manera ordenada. Consulte el enfoque recursivo de esta publicación. Que la lista final obtenida sea la cabeza .
2. Quite los duplicados del encabezado de la lista ordenada ordenada .

// C++ implementation to merge two sorted linked list
// without duplicates
#include <bits/stdc++.h>
 
using namespace std;
 
// structure of a node
struct Node {
    int data;
    Node* next;
};
 
// function to get a new node
Node* getNode(int data)
{
    // allocate space
    Node* temp = (Node*)malloc(sizeof(Node));
 
    // put in data
    temp->data = data;
    temp->next = NULL;
    return temp;
}
 
// function to merge two sorted linked list
// in a sorted manner
Node* sortedMerge(struct Node* a, struct Node* b)
{
    Node* result = NULL;
 
    /* Base cases */
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);
 
    /* Pick either a or b, and recur */
    if (a->data <= b->data) {
        result = a;
        result->next = sortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = sortedMerge(a, b->next);
    }
    return (result);
}
 
/* The function removes duplicates from a sorted list */
void removeDuplicates(Node* head)
{
    /* Pointer to traverse the linked list */
    Node* current = head;
 
    /* Pointer to store the next pointer of a node to be deleted*/
    Node* next_next;
 
    /* do nothing if the list is empty */
    if (current == NULL)
        return;
 
    /* Traverse the list till last node */
    while (current->next != NULL) {
 
        /* Compare current node with next node */
        if (current->data == current->next->data) {
 
            /* The sequence of steps is important*/
            next_next = current->next->next;
            free(current->next);
            current->next = next_next;
        }
        else /* This is tricky: only advance if no deletion */
        {
            current = current->next;
        }
    }
}
 
// function to merge two sorted linked list
// without duplicates
Node* sortedMergeWithoutDuplicates(Node* head1, Node* head2)
{
    // merge two linked list in sorted manner
    Node* head = sortedMerge(head1, head2);
 
    // remove duplicates from the list 'head'
    removeDuplicates(head);
 
    return head;
}
 
// function to print the linked list
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
 
// Driver program to test above
int main()
{
    // head1: 1->1->4->5->7
    Node* head1 = getNode(1);
    head1->next = getNode(1);
    head1->next->next = getNode(4);
    head1->next->next->next = getNode(5);
    head1->next->next->next->next = getNode(7);
 
    // head2: 2->4->7->9
    Node* head2 = getNode(2);
    head2->next = getNode(4);
    head2->next->next = getNode(7);
    head2->next->next->next = getNode(9);
 
    Node* head3;
 
    head3 = sortedMergeWithoutDuplicates(head1, head2);
 
    printList(head3);
 
    return 0;
}

// Java implementation to merge two sorted linked list
// without duplicates
import java.io.*;
 
class GFG {
 
    // structure of a node
    class Node {
        int data;
        Node next;
    }
 
    // function to get a new node
    public Node getNode(int data)
    {
        Node temp = new Node();
        temp.data = data;
        temp.next = null;
        return temp;
    }
 
    // function to merge two sorted linked list in a sorted
    // manner
    static Node sortedMerge(Node a, Node b)
    {
        Node result = null;
        /* Base cases */
        if (a == null) {
            return b;
        }
        else if (b == null) {
            return a;
        }
        /* Pick either a or b, and recur */
        if (a.data <= b.data) {
            result = a;
            result.next = sortedMerge(a.next, b);
        }
        else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }
        return result;
    }
 
    /* The function removes duplicates from a sorted list */
    static void removeDuplicates(Node head)
    {
        /* Pointer to traverse the linked list */
        Node current = head;
       
        /* Pointer to store the next pointer of a node to be
         * deleted*/
        Node next_next;
 
        /* do nothing if the list is empty */
        if (current == null) {
            return;
        }
 
        /* Traverse the list till last node */
        while (current.next != null)
        {
           
            /* Compare current node with next node */
            if (current.data == current.next.data)
            {
               
                /* The sequence of steps is important*/
                next_next = current.next.next;
                current.next = next_next;
            }
            else { /* This is tricky: only advance if no
                      deletion */
                current = current.next;
            }
        }
    }
 
    // function to merge two sorted linked list without
    // duplicates
    public Node sortedMergeWithoutDuplicates(Node head1,
                                             Node head2)
    {
 
        // merge two linked list in sorted manner
        Node head = sortedMerge(head1, head2);
 
        // remove duplicates from the list 'head'
        removeDuplicates(head);
 
        return head;
    }
 
    // function to print the linked list
    public void printList(Node head)
    {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
 
    public static void main(String[] args)
    {
 
        GFG l = new GFG();
 
        // head1 : 1->1->4->5->7
        Node head1 = l.getNode(1);
        head1.next = l.getNode(1);
        head1.next.next = l.getNode(4);
        head1.next.next.next = l.getNode(5);
        head1.next.next.next.next = l.getNode(7);
 
        // head2 : 2->4->7->9
        Node head2 = l.getNode(2);
        head2.next = l.getNode(4);
        head2.next.next = l.getNode(7);
        head2.next.next.next = l.getNode(9);
 
        Node head3;
 
        head3
            = l.sortedMergeWithoutDuplicates(head1, head2);
 
        l.printList(head3);
    }
}
 
// This code is contributed by lokeshmvs21.

# Python3 implementation to merge two
# sorted linked list without duplicates
  
# Structure of a node
class Node:
     
    def __init__(self, data):
         
        self.data = data
        self.next = None
  
# Function to get a new node
def getNode(data):
     
    # Allocate space
    temp = Node(data)
    return temp
 
# Function to merge two sorted linked
# list in a sorted manner
def sortedMerge(a, b):
     
    result = None
  
    # Base cases
    if (a == None):
        return(b)
    elif (b == None):
        return(a)
  
    # Pick either a or b, and recur
    if (a.data <= b.data):
        result = a
        result.next = sortedMerge(a.next, b)
    else:
        result = b
        result.next = sortedMerge(a, b.next)
 
    return(result)
     
# The function removes duplicates
# from a sorted list
def removeDuplicates(head):
 
    # Pointer to traverse the linked list
    current = head
  
    # Pointer to store the next pointer
    # of a node to be deleted
    next_next = None
  
    # Do nothing if the list is empty
    if (current == None):
        return
  
    # Traverse the list till last node
    while (current.next != None):
  
        # Compare current node with next node
        if (current.data == current.next.data):
  
            # The sequence of steps is important
            next_next = current.next.next
            del (current.next)
            current.next = next_next
        else:
             
            # This is tricky: only advance
            # if no deletion
            current = current.next
     
# Function to merge two sorted linked list
# without duplicates
def sortedMergeWithoutDuplicates(head1, head2):
 
    # Merge two linked list in sorted manner
    head = sortedMerge(head1, head2)
  
    # Remove duplicates from the list 'head'
    removeDuplicates(head)
  
    return head
 
# Function to print the linked list
def printList(head):
 
    while (head != None):
        print(head.data, end = ' ')   
        head = head.next
     
# Driver code
if __name__=='__main__':
     
    # head1: 1.1.4.5.7
    head1 = getNode(1)
    head1.next = getNode(1)
    head1.next.next = getNode(4)
    head1.next.next.next = getNode(5)
    head1.next.next.next.next = getNode(7)
  
    # head2: 2.4.7.9
    head2 = getNode(2)
    head2.next = getNode(4)
    head2.next.next = getNode(7)
    head2.next.next.next = getNode(9)
  
    head3 = sortedMergeWithoutDuplicates(
        head1, head2)
  
    printList(head3)
  
# This code is contributed by rutvik_56

Producción: 

1 2 4 5 7 9

Complejidad temporal: O(n1 + n2). 
Espacio Auxiliar: O(1).

Ejercicio: obtenga la lista enlazada ordenada final sin duplicados en un solo recorrido de las dos listas.