c++ 取兩個(gè)鏈表的交集

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

問題陳述：編寫一個(gè)C ++程序來查找兩個(gè)單個(gè)鏈表的交集。

Example:

例：

Let the first linked list be:6->5->2->9->NULLLet the second linked list to be:2->7->NULLSo 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.

一種技術(shù)可以是遍歷鏈表的所有節(jié)點(diǎn)，并檢查遍歷的節(jié)點(diǎn)是否在另一鏈表中。 這種方法需要O(m * n)乘以復(fù)雜度 。 m ， n =鏈表的長(zhǎng)度 。

Efficient approach:

高效的方法：

Efficient approach use to use merge sort.

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

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

使用合并排序?qū)蓚€(gè)鏈表進(jìn)行排序。 (有關(guān)詳細(xì)信息，請(qǐng)參閱： 合并單個(gè)鏈接列表的排序 )

Scan each linked list and build intersection according to following:

掃描每個(gè)鏈表并按照以下步驟建立交集：

IF (list1->data < list2->data)No intersection foundTraverse list1 by one step( list1=list1->next) ELSE IF(list1->data ==list2->data)Createnode(list1->data) && append node to the intersection listTraverse list1 by one step( list1=list1->next)Traverse list2 by one step( list2=list2->next) ELSE//list1->data >list2->dataNo intersection foundTraverse list2 by one step( list2=list2->next) END IF-ELSE

Display the intersection list

顯示路口清單

.minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}} .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}}

C ++實(shí)現(xiàn)查找兩個(gè)鏈表的交集 (C++ implementation to find intersection of two linked lists)

#include<bits/stdc++.h> using namespace std;class node{public:int data; // data fieldstruct node *next; };void display(class node* head){node* current=head; // current node set to head//traverse until current node isn't NULLwhile(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 casesif(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;//splitingslow->next=NULL; }//merge sort void mergeSort(node** refToHead){ node* head=*refToHead;node* split1,*split2;//base caseif(head==NULL || head->next==NULL){return;}//split the list in two halvessplitList(head,&split1,&split2);//recursively sort the two halvesmergeSort(&split1);mergeSort(&split2);*refToHead=mergeList(split1,split2);return; }node* findIntersection(node* head1, node* head2){//base caseif(head1==NULL && head2==NULL)return NULL;node* head4=NULL,*temp;//for inserting the first common nodewhile( 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 nodeselse 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 nodescanf("%d",&k);temp=head1;///inserting at the end//while(k){curr=creatnode(k);temp->next=curr;//appending each nodetemp=temp->next;scanf("%d",&k);}cout<<"displaying list1...\n";display(head1); // displaying the listcout<<"\nenter list2...\n";scanf("%d",&k);node* head2=creatnode(k); //buliding list, first nodescanf("%d",&k);temp=head2;///inserting at the end//while(k){curr=creatnode(k);temp->next=curr;//appending each nodetemp=temp->next;scanf("%d",&k);}cout<<"displaying list1...\n";display(head2);//sort both the listsmergeSort(&head1);mergeSort(&head2);cout<<"\ndisplaying their intersection...\n";node* head4=findIntersection(head1,head2);if(head4)display(head4);elsecout<<"No intersection found\n";return 0; }

Output

輸出量

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 .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}} .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}}

Example with explanation:

帶有說明的示例：

First linked list: 6->5->2->9->NULL Second linked list: 2->7->NULLAfter 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):0^th 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;1^st 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;2^nd iteration head1!=NULL && head2!=NULL thushead1=6->next=9; temp=same as before intersection list up to now: 2->NULL head2=same as before;3^rd 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;4^th iteration Head2=NULL So, iteration stops & intersection list is build: 2->NULL

翻譯自: https://www.includehelp.com/cpp-programs/find-intersection-of-two-linked-lists.aspx

c++ 取兩個(gè)鏈表的交集

總結(jié)

以上是生活随笔為你收集整理的c++ 取两个链表的交集_使用C ++程序查找两个链表的交集的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。