c++ 取两个链表的交集

Problem statement: Write a C++ program to find the intersection of two single linked lists.

问题陈述：编写一个C ++程序来查找两个单个链表的交集。

Example:

例：

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

Solution

解

Brute force approach:

蛮力法：

One technique can be to traverse all the nodes of a linked list and check whether the traversed node is in the other linked list or not. Such an approach takes O(m*n) times complexity. m, n=length of linked lists.

一种技术可以是遍历链表的所有节点，并检查遍历的节点是否在另一链表中。 这种方法需要O(m * n)乘以复杂度 。 m ， n =链表的长度 。

Efficient approach:

高效的方法：

Efficient approach use to use merge sort.

高效的方法用于使用合并排序 。

1. Sort both the linked list using merge sort. ( for detailed refer to: )

   使用合并排序对两个链表进行排序。 (有关详细信息，请参阅： )

2. Scan each linked list and build intersection according to following:

   扫描每个链表并按照以下步骤建立交集：

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. Display the intersection list

   显示路口清单

C ++实现查找两个链表的交集 (C++ implementation to find intersection of two linked lists)

#include
    
     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 sortvoid 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 sortvoid 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
     
      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
      
       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 end\n");	printf("enter 0 to stop building the list, else enter any integer\n");	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 found\n";	return 0;}
      
     
    

Output

输出量

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

Example with explanation:

带有说明的示例：

First linked list: 6->5->2->9->NULLSecond linked list: 2->7->NULLAfter applying merge sort:First linked list: 2->5->6->9->NULLSecond linked list: 2->7->NULL------------------------------------------------------//for better understanding nodes are represented //only by respective valueshead1=2head2=2FindIntersection(2,2):0th iterationhead1!=NULL && head2!=NULLhead1->data==head2->data //=2thus head4(head of intersection list) =2temp=head4=2intersection list up to now:2->NULLhead1=2->next=5;head2=2->next=7;1st iterationhead1!=NULL && head2!=NULLhead1->data
    
     data //5<7thushead1=5->next=6;temp=same as beforeintersection list up to now:2->NULLhead2=same as before;2nd iterationhead1!=NULL && head2!=NULLthushead1=6->next=9;temp=same as beforeintersection list up to now:2->NULLhead2=same as before;3rd iterationhead1!=NULL && head2!=NULLhead1->data>head2->data //9>7thushead2=7->next=NULL;temp=same as beforeintersection list up to now:2->NULLHead1=same as before;4th iterationHead2=NULLSo, iteration stops & intersection list is build:2->NULL
    

翻译自:

c++ 取两个链表的交集