算法题：求解两个链表的交集
分类：算法
链表交集
/*已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A = { 5, 10, 20, 15, 25, 30 }，，集合B = { 5, 15, 35, 25 }，完成计算后A = { 10, 20, 30 }。*/#include <iostream>using namespace std;struct Node{int data;Node *next;Node(int d = int()):data(d),next(NULL){}};class List{public:List(int a[],int n):head(NULL){int i = 0;Node *p = NULL;for (; i<n; i++){Node *s = new Node(a[i]);if (head == NULL){head = s;p = head;s = p;}else{s->next = p->next;p->next = s;p = s;}}}void difference(const List &list)//求交集。{Node *pA = head;Node *pB = list.head;Node *savP=NULL;if (pA == NULL || pB == NULL){head = NULL;return;}Node *temp=NULL;while (pA != NULL && pB!=NULL){while (pA->data < pB->data){pA=pA->next;if (pA == NULL)return;}while (pA->data > pB->data){pB=pB->next;if (pB == NULL)return;}if (pA->data == pB->data){Node *m = pA->next;if (savP == NULL){savP = pA;savP->next = NULL;}else{temp = savP;while (temp->next != NULL){temp = temp->next;}pA->next = NULL;temp->next = pA;}pA=m;pB=pB->next;}}head = savP;}void Printf(){Node *p = head;while (p != NULL){cout << p->data << “—->”;p = p->next;}cout << endl;}private:Node *head;};int main(){int a[] = {1,2,3,4,5,6,7,8,9};int b[] = {4,5,6,7,8,9,10};List list1(a, sizeof(a) / sizeof(int));List list2(b, sizeof(b) / sizeof(int));list1.difference(list2);list1.Printf();list2.Printf();return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇算法题：压缩任意字符串下一篇算法题：链表的递归逆序
顶1踩0
相信人生有挫折没有失败，相信生命的质量来自决不妥协的信念。
