List-LinkedList-求两个单链表的交集

基于单链表实现集合的交集、并集、差集的运算解题思路（单链表求交集、并集、差集的思想和顺序表求交集、并集、差集的思想基本相同）1.先通过CreateListR 函数将集合 a 和 b 中的元素添加到顺序表 ha 和 hb 中，添加过程使⽤的是顺序表原有的Initlist 函数（初始化表）和ListInsert 函数（向表中插⼊元素）。

2.因为原集合是⽆序的，所以我通过 sort 函数（选择排序），使得集合变得有序。

3.得到有序集合 ha 和 hb 后，便可以使⽤ Union 函数（类似归并的思想写出来的求并集的函数），求出 ha 和 hb 的并集。

4.⽽求交集的⽅法则是，通过将集合 a 中的元素⼀个⼀个取出，并通过函数LocateElem ，查看集合 hb 中是否存在该元素，如果存在则将元素放⼊ hc ，如果不存在，则舍去。

以此求得两集合的交集。

5.求两集合的差则可以反过来，同样通过将集合 a 中的元素⼀个⼀个取出，并通过函数LocateElem ，查看集合 hb 中是否存在该元素，如果不存在则将元素放⼊ hc ，如果存在，则舍去。

以此求得两集合的差集。

#include <iostream>#include <cstdio>#include <malloc.h>using namespace std;/* 定义单链表数据 */typedef char ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LinkList;/* 单链表的初始化 */void InitList(LinkList *&L){L = (LinkList *)malloc(sizeof(LinkList));L->next=NULL;}/* 向单链表中插⼊数据元素 */bool ListInsert(LinkList *&L,int x,char e){int j = 0;LinkList *p = L, *s;while(p!=NULL && j<x-1){p = p->next;j++;}if(p==NULL){return false;}else{s = (LinkList *)malloc(sizeof(LinkList));s->data = e;s->next = p->next;p->next = s;return true;}}/* 输出单链表 */void DispList(LinkList *L){LinkList *p = L->next;while(p!=NULL){printf("%c ",p->data);p = p->next;}printf("\n");}/* 求单链表的长度 */int ListLength(LinkList *L){LinkList *p = L->next;int i = 0;while(p!=NULL){p = p->next;}return i;}/* 查看单链表是否为空 */bool ListEmpty(LinkList *L){return L->next==NULL;}/* 求单链表中某个数据元素值 */bool GetElem(LinkList *L,int i, ElemType &e) {LinkList *p = L;int j = 0;while(p!=NULL && j < i){p=p->next;j++;}if(p==NULL){return false;}else{e = p->data;return true;}}/* 在单链表中查找元素 */int LocateElem(LinkList *L,ElemType e){LinkList *p = L;int i = 0;while(p!=NULL && p->data!=e){p = p->next;i++;}if(p==NULL){return0;}else{return i;}}/* 删除单链表中第 i 个元素*/bool ListDelete(LinkList *&L,int i,ElemType &e) {int j = 0;LinkList *p = L, *q;while(p!=NULL && j < i - 1){p = p->next;j++;}if(p==NULL)return false;else{q = p->next;if(q==NULL)return false;e = q->data;p->next = q->next;free(q);return true;}}/* 删除单链表 */void DestroyList(LinkList *&L){LinkList *p = L;LinkList *q = p->next;while(q!=NULL){p = q;q = p->next;}free(p);}void CreateListR(LinkList *&L,ElemType e[],int n) {InitList(L);int i;for(i = 0;i < n; ++i){if(!LocateElem(L,e[i]))ListInsert(L,i+1,e[i]);}}void InsterSect(LinkList *a,LinkList *b,LinkList *&c) {DestroyList(c);InitList(c);LinkList *p = a->next;int i = 0;while(p!=NULL){if(LocateElem(b,p->data))ListInsert(c,++i,p->data);p = p->next;}}void Subs(LinkList *a,LinkList *b,LinkList *&c){DestroyList(c);InitList(c);LinkList *p = a->next;int i = 0;while(p!=NULL){if(!LocateElem(b,p->data))ListInsert(c,++i,p->data);p = p->next;}}void Union(LinkList *a,LinkList *b,LinkList *&c){InitList(c);LinkList *p = a->next;LinkList *q = b->next;int k = 0;while(p!=NULL && q!=NULL){if(p->data < q->data){ListInsert(c,k+1,p->data);p = p->next;k++;}else if(p->data == q->data){ListInsert(c,k+1,p->data);p = p->next;q = q->next;k++;}else{ListInsert(c,k+1,q->data);q = q->next;k++;}}while(p!=NULL){ListInsert(c,k+1,p->data);p = p->next;k++;}while(q!=NULL){ListInsert(c,k+1,q->data);q = q->next;}///cout<<"hehe"<<endl;}void sort(LinkList *&L){LinkList *p , *pre, *q, *k;InitList(p);int i = 0;char c;while(!ListEmpty(L)){pre = L ->next;c = pre->data;while(pre!=NULL){if(c>=pre->data)c = pre->data;pre = pre->next;}ListInsert(p,++i,c);int tag = LocateElem(L,c);ListDelete(L,tag,c);}L = p;}int main( ){LinkList *ha, *hb, *hc;ElemType a[]={'c','a','e','h'};ElemType b[]={'f','h','b','g','d','a'};printf("集合的运算如下\n");CreateListR(ha,a,4);CreateListR(hb,b,6);printf("原集合 A: "); DispList(ha); printf("原集合 B: "); DispList(hb); sort(ha);sort(hb);printf("有序集合A："); DispList(ha); printf("有序集合B："); DispList(hb); Union(ha,hb,hc);printf("集合的并C："); DispList(hc); InsterSect(ha,hb,hc);printf("集合的交C："); DispList(hc); Subs(ha,hb,hc);printf("集合的差C："); DispList(hc); DestroyList(ha);DestroyList(hb);DestroyList(hc);return0;}。

单链表求集合的并、交和差运算单链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

在计算机科学中，我们经常需要对集合进行操作，包括求并集、交集和差集。

在本文中，我们将介绍如何使用单链表来实现这些集合操作。

我们需要定义一个单链表的数据结构。

每个节点包含一个数据元素和一个指向下一个节点的指针。

我们可以使用类来实现这个数据结构，例如：```class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None```接下来，我们需要实现集合的并、交和差运算。

首先是并运算，它将两个集合中的所有元素合并为一个新的集合。

我们可以使用两个指针分别遍历两个链表，将两个链表中的元素逐个比较，并将不重复的元素添加到结果链表中。

具体代码如下：```def union(l1, l2):result = LinkedList()p1 = l1.headp2 = l2.headwhile p1 is not None:result.append(p1.data)p1 = p1.nextwhile p2 is not None:if not result.contains(p2.data):result.append(p2.data)p2 = p2.nextreturn result```接下来是交运算，它将两个集合中共有的元素提取出来组成一个新的集合。

同样地，我们可以使用两个指针分别遍历两个链表，将相同的元素添加到结果链表中。

具体代码如下：```def intersection(l1, l2):result = LinkedList()p1 = l1.headwhile p1 is not None:if l2.contains(p1.data):result.append(p1.data)p1 = p1.nextreturn result```最后是差运算，它将第一个集合中不属于第二个集合的元素提取出来组成一个新的集合。

List-LinkedList-链表的逆向合并假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A和B 表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的节点空间构造C表#include <stdio.h> #include <malloc.h>typedef struct ListNode { //定义链表节点int data;struct ListNode *next;} ListNode, *LinkedList;void initLinkedList(LinkedList &linkedList, int len) { //初始化链表linkedList = (LinkedList)malloc(sizeof(ListNode)); linkedList->next = NULL;int i; LinkedList p;for(i=len; i>0; i--) {p = (LinkedList)malloc(sizeof(ListNode)); p->data = i;p->next = linkedList->next; linkedList->next = p;}}void printLinkedList(LinkedList linkedList) { //打印链表中的数据if(!linkedList) return ;else if(!linkedList->next) return ;LinkedList p = linkedList->next;while(p) {printf("%d ", p->data); p = p->next;}printf("\n");}void onLocReverse(LinkedList &C) { //就地求反LinkedList head = C;LinkedList t1, t2;t1 = head->next; t2 = t1->next; t1->next = NULL;while(t2->next) {t1 = t2; t2 = t2->next; t1->next = head->next; head->next = t1;}t2->next = t1; head->next = t2;}void mergeLinkedList(LinkedList &A, LinkedList &B, LinkedList &C) { //A和B合并成CLinkedList pa, pb, pc;pa = A->next; pb = B->next; C = pc = A; free(B);while(pa && pb) {if(pa->data < pb->data) {pc->next = pa; pc = pa; pa = pa->next;} else {pc->next = pb; pc = pb; pb = pb->next;}}pc->next = pa ? pa : pb;onLocReverse(C);}void main() {LinkedList A, B, C;initLinkedList(A, 10); initLinkedList(B, 8);printf("A链表的值为:"); printLinkedList(A);printf("B链表的值为:"); printLinkedList(B);mergeLinkedList(A, B, C);printf("合并后C链表的值为："); printLinkedList(C); }。

题目：两个单向链表，找出它们的第一个公共结点。

链表的结点定义为：struct ListNode{int m_nKey;ListNode* m_pNext;};分析：这是一道微软的面试题。

微软非常喜欢与链表相关的题目，因此在微软的面试题中，链表出现的概率相当高。

如果两个单向链表有公共的结点，也就是说两个链表从某一结点开始，它们的m_pNext 都指向同一个结点。

但由于是单向链表的结点，每个结点只有一个m_pNext，因此从第一个公共结点开始，之后它们所有结点都是重合的，不可能再出现分叉。

所以，两个有公共结点而部分重合的链表，拓扑形状看起来像一个Y，而不可能像X。

看到这个题目，第一反应就是蛮力法：在第一链表上顺序遍历每个结点。

每遍历一个结点的时候，在第二个链表上顺序遍历每个结点。

如果此时两个链表上的结点是一样的，说明此时两个链表重合，于是找到了它们的公共结点。

如果第一个链表的长度为m，第二个链表的长度为n，显然，该方法的时间复杂度为O(mn)。

接下来我们试着去寻找一个线性时间复杂度的算法。

我们先把问题简化：如何判断两个单向链表有没有公共结点？前面已经提到，如果两个链表有一个公共结点，那么该公共结点之后的所有结点都是重合的。

那么，它们的最后一个结点必然是重合的。

因此，我们判断两个链表是不是有重合的部分，只要分别遍历两个链表到最后一个结点。

如果两个尾结点是一样的，说明它们用重合；否则两个链表没有公共的结点。

在上面的思路中，顺序遍历两个链表到尾结点的时候，我们不能保证在两个链表上同时到达尾结点。

这是因为两个链表不一定长度一样。

但如果假设一个链表比另一个长l个结点，我们先在长的链表上遍历l个结点，之后再同步遍历，这个时候我们就能保证同时到达最后一个结点了。

由于两个链表从第一个公共结点考试到链表的尾结点，这一部分是重合的。

因此，它们肯定也是同时到达第一公共结点的。

于是在遍历中，第一个相同的结点就是第一个公共的结点。

list 对象集合取交集取并集工具类标题：深入探讨List对象集合取交集、取并集的工具类在日常开发中，List对象集合的操作是非常常见的。

其中，取交集、取并集是List集合操作中的重要部分。

为了更高效地进行这些操作，我们通常会使用工具类来实现。

本文将从简单到复杂，由浅入深地探讨List对象集合取交集、取并集的工具类，并分享个人的观点和理解。

1. 介绍List对象集合在编程中，List是一种常见的数据结构，用于存储一组有序的数据。

它允许我们按照插入顺序来访问元素，并且可以包含重复的元素。

在Java中，List是一个接口，常用的实现类有ArrayList和LinkedList。

除了Java，其他编程语言中也有类似的数据结构，如Python的列表(List)、C#的列表(List)等。

2. 取交集的工具类实现取交集是指找出多个集合中相同的元素，Java中可以使用retainAll方法来实现List集合的取交集操作。

除了使用retainAll方法，我们还可以编写工具类来更灵活地实现取交集的操作。

下面是一个简单的取交集工具类示例：```javapublic class ListUtils {public static List<Integer> intersection(List<Integer> list1, List<Integer> list2) {List<Integer> result = new ArrayList<>(list1);result.retainAll(list2);return result;}}```在这个示例中，我们使用retainAll方法实现了取交集的功能，并将结果保存在一个新的List中返回。

这样，我们可以在其他地方多次使用这个工具类来取两个List的交集。

3. 取并集的工具类实现取并集是指将多个集合中的元素合并，并去除重复的元素。

顺序表和链式表求并集交集和差集/*系统总体说明：用顺序表和单链表分别实现求集合的并集、交集和差集。

完成功能的详细说明：1．将集合当成一个线性表。

2．输入并创建集合，分别以顺序表和链表作为存储结构。

3．实现两个集合的并集、交集和差集运算。

4．显示集合，查看运算结果。

5．用户界面包括以下功能：创建\交集\并集\差集\显示\退出交：从一个集合中取出一个元素，在另一个集合中查找，如果有它就是交中的元素，如果没有再从第一个集合中取出第二个元素，如此进行，知道第一个集合中的元素全部取遍得到的就是这两个元素的交。

并：并也类似，关键就是判断这个元素是否都在这两个集合中出现。

差：差更简单，就是交中判断是否是第二个集合中元素的结果想反*/#include#include#includeusing namespace std;typedef int DataType;#define MAXSIZE 10typedef struct //顺序表的定义{DataType data[MAXSIZE+MAXSIZE];int len; //顺序表的长度}seqList;void Init_seqList(seqList &L) //顺序表的初始化{cout<<"初始化成功！"<<endl;< p="">L.len=0;}void set_seqList(seqList &L) //顺序表中输入集合的元素{int len;DataType a;int i=0;cout<<"输入线性表的长度为：" <<endl;< p=""> cin>>len;cout<<"输入线性表的元素为："<<endl;< p="">while(i<len)< p="">{if(L.len>=MAXSIZE){cout<<"输入的值超出了范围。

⽤链表实现集合的交集并集差集运算题⽬来⾃某NJU同学的程序设计基础作业贴⼀下题⽬：⽤链表建⽴两个整数集合A和B（从键盘键⼊集合的元素，以-1结束，集合中没有-1）。

分别编写三个函数计算这两个集合的。

a.交集 b.并集 c.差集A-B三个函数的计算结果为新的链表。

输出这三个新链表。

做题⼼得其实这道题⽤数组直接能秒杀掉，难度就在对于单链表的理解与应⽤。

对指针和结构体有挺⾼的掌握要求。

之前没好好学链表，总觉得数组能解决的事⽤数组，数组解决不了的⽤STL(stl永远的神不接受反驳)补了三天的链表，总算学得明⽩了⼀点，简单把题过了⼀下。

没有⽤函数分段，其实分段⼀下很简单。

P.S肥肠感谢鸡哥龙神的⿍⼒相助！直接po代码，有错误或者其他更好的思路也希望dalao们可以带带#include<stdio.h>#include<stdlib.h>struct node//链表结构体{int data;//数据域struct node* next;//指向下⼀个结构体的指针};node* create(int data)//新建链表项（新结构体）{node* newNode = (node*)malloc(sizeof(node));//给这个结构体开空间newNode->data = data;//保存数据newNode->next = NULL;//指针为空return newNode;//返回新建的结构体}int main(){struct node *p,*q,*t,*h;//定义⼏个临时变量，会⽤到int tmp;//输⼊集合Ascanf("%d", &tmp);struct node* head_a = create(tmp);//头节点p = head_a;//p是临时变量while (scanf("%d", &tmp) && tmp != -1)//输⼊数字，且当tmp=-1的时候结束{struct node* a = create(tmp);//给链表A新建节点p->next = a;//上⼀个节点的指针指向现在这个p = a;//临时变量变成现在这个}//输⼊集合Ascanf("%d", &tmp);struct node* head_b = create(tmp);//头节点p = head_b;//p是临时变量while (scanf("%d", &tmp) && tmp != -1)//输⼊数字，且当tmp=-1的时候结束{struct node* b = create(tmp);//给链表A新建节点p->next = b;//上⼀个节点的指针指向现在这个p = b;//临时变量变成现在这个}struct node* head_jiao = create(-1);//定义交集的头结点struct node* head_bing = create(-1);//定义并集的头结点struct node* head_cha = create(-1);//定义差集的头结点/*交集思路：遍历A，对A的每个元素，都与B中的元素进⾏⼀⼀对⽐类似于for循环中的for(int i=0;i<n;i++){for(int j=0;j<m;j++){⽐较a和b}}*/p=head_a;//p是临时变量，从A的头开始t=head_jiao;//t是临时变量，⽤来存交集的链表while(p!=NULL)//链表A⾮空，遍历A链表{q=head_b;//q是临时变量，从B的头开始while(q!=NULL)//链表B⾮空，遍历B链表{if(q->data==p->data)//B元素=A元素{//如果a和b中有相同元素，则存进交集链表中//以下操作与输⼊A,B集合同原理struct node* jiao = create(p->data);t->next = jiao;t = jiao;break;//因为找到了，所以break掉，去⽐较A的下⼀个元素}q=q->next;//链表B的当前位置后移（q->next是下⼀个元素，让q=下⼀个元素 }p=p->next;//链表A的当前位置后移（p->next是下⼀个元素，让p=下⼀个元素 }/*输出交集因为head_jiao->data头节点的数据域中存的是-1（见上⽂定义交集头结点故从head_jiao的下⼀个开始*/t=head_jiao->next;while(t!=NULL)//遍历交集链表{printf("%d ",t->data);//输出元素，记得加空格t=t->next;//后移}//Attention:这个-1不应该被放在链表中printf("-1\n");//最后的元素以-1结尾，记得加换⾏/*并集思路：先复制A的所有元素在并集bing⾥⾯然后遍历B，将B的每⼀个元素都与bing中元素⽐较若⽐较到最后都不⼀样，则当前元素不在bing中将这个元素添加进bing的末尾*/p=head_a;//p是临时变量，从A的头开始t=head_bing;//t是临时变量，⽤来存并集的链表while(p!=NULL)//遍历链表A{//以下操作与输⼊A,B集合同理，使⽤链表A的数据struct node* bing = create(p->data);t->next = bing;t = bing;p=p->next;//链表A的当前位置后移（p->next是下⼀个元素，让p=下⼀个元素 }q=head_b;//q是临时变量，从B的头开始while(q!=NULL)//遍历链表B{h=head_bing;//h是临时变量，读取并集的链表int flag=0;//⽤flag来记录是否有相同元素while(h!=NULL)//遍历并集{if(h->data==q->data)//存在相同元素{flag=1;break;}h=h->next;//后移}if(!flag)//如果不存在相同元素{//以下操作与输⼊A,B集合同理，使⽤链表B的当前元素数据//t还是上⾯复制的时候定义的那个，继续相同操作struct node* bing = create(q->data);t->next = bing;t = bing;}q=q->next;//后移}/*输出并集因为head_bing->data头节点的数据域中存的是-1（见上⽂定义并集头结点故从head_bing的下⼀个开始*/t=head_bing->next;while(t!=NULL)//遍历并集链表{printf("%d ",t->data);//输出元素，记得加空格t=t->next;//后移}//Attention:这个-1不应该被放在链表中printf("-1\n");//最后的元素以-1结尾，记得加换⾏/*差集思路：同并集，先复制链表A在链表cha⾥⾯再遍历链表bing，如果遇到元素在链表A中，则删除链表节点*/p=head_a;//p是临时变量，从A的头开始t=head_cha;//t是临时变量，⽤来存差集的链表while(p!=NULL)//遍历链表A{//以下操作与输⼊A,B集合同理，使⽤链表A的数据struct node* cha = create(p->data);t->next = cha;t = cha;p=p->next;//链表A的当前位置后移（p->next是下⼀个元素，让p=下⼀个元素 }q=head_jiao;//q是临时变量，从jiao的头开始while(q!=NULL)//遍历链表jiao{h=head_cha;//h是临时变量，从cha的第1个开始t=head_cha->next;//t是临时变量，从cha的第2个开始while(t!=NULL)//遍历cha差集，寻找当前数，然后把它删了{if(t->data==q->data)//如果相等，删除{h->next=t->next;//跳过t指向下⼀个break;}//如果没删除，后移h=h->next;t=t->next;}q=q->next;//后移}/*输出差集因为head_cha->data头节点的数据域中存的是-1（见上⽂定义并集头结点故从head_cha的下⼀个开始*/t=head_cha->next;while(t!=NULL)//遍历差集链表{printf("%d ",t->data);//输出元素，记得加空格t=t->next;//后移}//Attention:这个-1不应该被放在链表中printf("-1\n");//最后的元素以-1结尾，记得加换⾏return0;}代码与解析。

list集合的交集方法摘要：1.介绍集合交集的概念2.常用集合交集算法概述3.举例说明集合交集的应用4.总结与展望正文：集合交集是指两个或多个集合中共同拥有的元素组成的集合。

在计算机科学和数据处理领域，集合交集有着广泛的应用。

本文将简要介绍集合交集的概念，并阐述常用的集合交集算法，最后通过实例来说明集合交集的应用。

一、集合交集的概念在数学中，集合交集的定义如下：设A、B是两个集合，它们的交集记为A∩B，表示包含在A和B中的共同元素组成的集合。

元素x属于A∩B当且仅当x同时属于A和B。

二、常用集合交集算法概述1.顺序查找法：顺序查找法是一种简单的集合交集算法，其主要思路是将两个集合中的元素逐一进行比较，找到共同拥有的元素。

该算法的时间复杂度为O(m+n)，其中m和n分别为两个集合的元素个数。

2.哈希表法：哈希表法是一种高效的集合交集算法，其主要思路是将两个集合分别存储在哈希表中，然后通过哈希表的查询操作找到共同拥有的元素。

该算法的时间复杂度为O(m+n)，其中m和n分别为两个集合的元素个数。

3.排序法：排序法是一种基于比较的集合交集算法，其主要思路是将两个集合排序后，使用双指针遍历两个有序集合，找到共同拥有的元素。

该算法的时间复杂度为O(nlogn)，其中n为两个集合的元素个数。

4.位运算法：位运算法是一种基于二进制表示的集合交集算法，其主要思路是将集合元素用二进制表示，然后通过位运算找到共同拥有的元素。

该算法的时间复杂度为O(m+n)，其中m和n分别为两个集合的元素个数。

三、集合交集应用实例假设有一个包含学生课程的集合，其中课程编号为1的课程有数学、英语、物理三门，课程编号为2的课程有数学、英语两门。

我们可以使用集合交集找到既有编号为1的课程又有编号为2的课程的学生。

设课程编号为1的学生集合为S1，课程编号为2的学生集合为S2，则S1∩S2即为既有编号为1的课程又有编号为2的课程的学生集合。

通过集合交集操作，我们可以得到如下结果：S1 = {1, 2, 3, 4, 5}S2 = {1, 2, 6, 7, 8}S1∩S2 = {1, 2}四、总结与展望集合交集在计算机科学和数据处理领域具有重要意义。

在Java中，可以使用多种方法获取两个数组的交集元素。

以下是其中几种常见的方法：1. 使用循环和条件判断：```javapublic static int[] getIntersection(int[] arr1, int[] arr2) {List<Integer> intersection = new ArrayList<>();for (int num : arr1) {for (int element : arr2) {if (num == element && !intersection.contains(num)) {intersection.add(num);break;}}}int[] result = new int[intersection.size()];for (int i = 0; i < intersection.size(); i++) {result[i] = intersection.get(i);}return result;}```2. 使用集合框架：```javapublic static int[] getIntersection(int[] arr1, int[] arr2) {Set<Integer> set1 = new HashSet<>();for (int num : arr1) {set1.add(num);}Set<Integer> set2 = new HashSet<>();for (int num : arr2) {set2.add(num);}set1.retainAll(set2);int[] result = new int[set1.size()];int index = 0;for (int num : set1) {result[index++] = num;}return result;}```3. 使用Java 8的Stream API：```javapublic static int[] getIntersection(int[] arr1, int[] arr2) {return Arrays.stream(arr1).distinct().filter(x -> Arrays.stream(arr2).anyMatch(y -> y == x)).toArray();}```这些方法都可以获取两个数组的交集元素，你可以根据自己的需求选择其中一种方法来使用。