Encuentra intersección de dos listas enlazadas mediante el programa C ++

En este artículo, vamos a ver cómo encontrar intersección de dos listas enlazadas de manera eficiente el uso de combinación de tipo ?

Planteamiento del problema: Escribir un programa en C ++ para encontrar la intersección de las dos listas enlazadas simples.

Ejemplo:

    Let the first linked list be:
6->5->2->9->NULL
Let the second linked list to be:
2->7->NULL
So there intersection is:
2->NULL

Solución

método de fuerza bruta:

Una técnica puede ser de atravesar todos los nodos de una lista enlazada y comprobar si el nodo atravesado está en el otra lista enlazada o no. Este enfoque lleva O (m * n) veces complejidad . m , n = longitud de listas enlazadas.

enfoque eficiente:

utilización enfoque eficiente para utilizar de combinación de tipo .

  1. Ordenar tanto la lista enlazada mediante fusión especie. (class detalla referirse a: Merge ordenar for individuales listas enlazadas)
  2. Scan cada lista enlazada y la intersección de construcción de acuerdo con la siguiente:
  3. IF (list1->data < list2->data)
    No intersection found
    Traverse list1 by one step( list1=list1->next)
    ELSE IF(list1->data ==list2->data)
    Createnode(list1->data) && append node to the intersection list
    Traverse list1 by one step( list1=list1->next)
    Traverse list2 by one step( list2=list2->next)
    ELSE//list1->data >list2->data
    No intersection found
    Traverse list2 by one step( list2=list2->next)
    END IF-ELSE

  4. Muestra la lista intersección

aplicación C ++ para encontrar intersección de dos listas enlazadas

#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data; // data field
struct node *next;
};
void display(class node* head){
node* current=head; // current node set to head
//traverse until current node isn't NULL
while(current!=NULL){
printf("%d ",current->data);
current=current->next; // go to next node
}
}
node* creatnode(int d){
node* temp=(node*)malloc(sizeof(node));
temp->data=d;
temp->next=NULL;
return temp;
}
//merging two sorted list
node* mergeList(node* split1,node* split2){
node* newhead=NULL;
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;
if(split1->data<=split2->data){
newhead=split1;
newhead->next=mergeList(split1->next,split2);
}
else{
newhead=split2;
newhead->next=mergeList(split1,split2->next);
}
return newhead;
}
//split list for merge sort
void splitList(node* head,node** split1,node** split2){
node* slow=head;
node* fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
*split1=head;
*split2=slow->next;
//spliting
slow->next=NULL;
}
//merge sort
void mergeSort(node** refToHead){
node* head=*refToHead;
node* split1,*split2;
//base case
if(head==NULL || head->next==NULL){
return;
}
//split the list in two halves
splitList(head,&split1,&split2);
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);
*refToHead=mergeList(split1,split2);
return;
}
node* findIntersection(node* head1, node* head2){
//base case
if(head1==NULL && head2==NULL)
return NULL;
node* head4=NULL,*temp;
//for inserting the first common node
while( head1!=NULL && head2!=NULL && head4==NULL){
if(head1->data<head2->data){
head1=head1->next;
}
//intersection nodes(intersection)
else if(head1->data==head2->data){
head4=creatnode(head1->data);
temp=head4;
head1=head1->next;
head2=head2->next;
}
else{
head2=head2->next;
}
}
//for other common nodes(intersection)
while( head1!=NULL && head2!=NULL){
if(head1->data<head2->data){
head1=head1->next;
}
//intersection nodes
else if(head1->data==head2->data){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
head2=head2->next;
}
else{
head2=head2->next;
}
}
return head4;
}
int main(){
printf("creating the linked list by inserting new nodes at the endn");
printf("enter 0 to stop building the list, else enter any integern");
int k;
node* curr,*temp;
cout<<"enter list1...n";
scanf("%d",&k);
node* head1=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head1;
///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"displaying list1...n";
display(head1); // displaying the list
cout<<"nenter list2...n";
scanf("%d",&k);
node* head2=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head2;
///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"displaying list1...n";
display(head2);
//sort both the lists
mergeSort(&head1);
mergeSort(&head2);
cout<<"ndisplaying their intersection...n";
node* head4=findIntersection(head1,head2);
if(head4)
display(head4);
else
cout<<"No intersection foundn";
return 0;
}

salida

First run:
creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
enter list1...
6 5 2 9 0
displaying list1...
6 5 2 9
enter list2...
2 7 0
displaying list1...
2 7
displaying their intersection...
2
Second run:
creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
enter list1...
6 7 8 0
displaying list1...
6 7 8
enter list2...
1 5 2 0
displaying list1...
1 5 2
displaying their intersection...
No intersection found

Ejemplo con la explicación:

First linked list: 6->5->2->9->NULL
Second linked list: 2->7->NULL
After applying merge sort:
First linked list: 2->5->6->9->NULL
Second linked list: 2->7->NULL
------------------------------------------------------
//for better understanding nodes are represented
//only by respective values
head1=2
head2=2
FindIntersection(2,2):
0th iteration
head1!=NULL && head2!=NULL
head1->data==head2->data //=2
thus head4(head of intersection list) =2
temp=head4=2
intersection list up to now:
2->NULL
head1=2->next=5;
head2=2->next=7;
1st iteration
head1!=NULL && head2!=NULL
head1->data<head2->data //5<7
thushead1=5->next=6;
temp=same as before
intersection list up to now:
2->NULL
head2=same as before;
2nd iteration
head1!=NULL && head2!=NULL
thushead1=6->next=9;
temp=same as before
intersection list up to now:
2->NULL
head2=same as before;
3rd iteration
head1!=NULL && head2!=NULL
head1->data>head2->data //9>7
thushead2=7->next=NULL;
temp=same as before
intersection list up to now:
2->NULL
Head1=same as before;
4th iteration
Head2=NULL
So, iteration stops & intersection list is build:
2->NULL


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *