6 求序列的交集（链表）

作者: Turbo时间限制: 1S章节: DS:数组和链表

问题描述

使用带头结点的单链表编程：有两个序列，分别表示两个集合。求它们的交集并输出。

输入说明

第一行输入序列A的信息： 第一个整数n(0<=n<=100)，表示共有n个元素，其后有n个整数，表示n个元素的数据 第一行输入序列B的信息： 第一个整数n(0<=n<=100)，表示共有n个元素，其后有n个整数，表示n个元素的数据

输出说明

输出交集的元素序列，输出格式见范例。 如果交集为空，则输出“head–>tail” 交集里的元素顺序，依照其在序列A中的顺序。 比如： 序列： A：5 3 2 7 B：1 3 5 8 则交集为5和3，因为在序列A中，5在3的前面，所以在交集里5也在3的前面。

输入范例

4 5 3 2 7 4 1 3 5 8

输出范例

head-->5-->3-->tail

解题思路

1.首先根据输入的数据用尾插法创建两个链表 2.求交集：对每一个a中节点都遍历一遍b链表，用flag标记是否找到值相等的节点，如果找到了中断遍历过程，如果没有找到就将该节点从a链表中删除掉。

详细实现

#include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; struct ListNode { int num; struct ListNode *next; }; ListNode *createByTail(int n) { ListNode *head=new ListNode; ListNode *p,*temp; p=head; head->next=NULL; int data,i; for(i=0;i<n;i++) { cin>>data; temp=new ListNode; temp->num=data; p->next=temp; p=temp; } p->next=NULL; return head; } ListNode *fun(ListNode *heada,ListNode *headb) { struct ListNode *p,*pre,*q; pre=heada; p=heada->next; while(p) { q=headb->next; int flag=0;//用来记录a链表中节点是否在b链表中存在 while(q) { if(q->num==p->num) { flag=1; break; } else q=q->next; } //不是公共节点 if(flag==0) { pre->next=p->next; free(p); p=pre->next; } else { pre=p; p=p->next; } } return heada; } void displayListNode(ListNode *head) { ListNode *p=head->next; cout<<"head-->"; while(p) { cout<<p->num<<"-->"; p=p->next; } cout<<"tail"<<endl; } int main() { int n,m; struct ListNode *heada,*headb; //创建两个链表 cin>>n; heada=createByTail(n); cin>>m; headb=createByTail(m); //对两个链表求交集 heada=fun(heada,headb); //输出就交集后的a链表 displayListNode(heada); return 0; }