已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。
可以利用循环的思想，创造出一个笛卡尔积的效果。当链表1中的每个节点，对应到链表2的每个节点进行寻找，找到数值相同的，则释放当前链表1的节点，并指向下一个节点。
#include<iostream> #include<stdlib.h> #include<assert.h> using namespace std; struct node { int elem; node* next; node(int x = 0) :elem(x) , next(NULL) {} }; node* Create(int *data,size_t size) { assert(data); node* head = new node(data[0]); int i = 1; node* pnode = NULL; node* ptemp = head; for (i; i < size;i++) { pnode = new node(data[i]); ptemp->next = pnode; ptemp = pnode; } return head; } void print(node *l) { assert(l); while (l) { cout << l->elem << " "; l = l->next; } cout << endl; } void difference(node** LA, node* LB) { node* pa = *LA; node* pb = LB; node* pre = NULL; node* temp = NULL; while (pa) { pb = LB;//保证每次从LB的第一个节点找起 while (pb&&pb->elem != pa->elem)//寻找PB中和PA相同的元素 pb = pb->next; if (pb)//找到了 { if (NULL == pre)//PA是头结点 *LA = pa->next; else { pre->next = pa->next;//连接前后节点 } temp = pa; pa = pa->next; free(temp); } else//没找到PA中的当前节点，继续寻找PA的下一个节点 { pre = pa; pa = pa->next; } } } int main() { int A[] = { 5, 10, 20, 15, 25, 30 }; int B[] = { 5, 15, 35, 25 }; int size1 = sizeof(A) / sizeof(A[0]); int size2 = sizeof(B) / sizeof(B[0]); node* L1 = Create(A,size1); node* L2 = Create(B,size2); print(L1); print(L2); difference(&L1,L2); print(L1); system("pause"); return 0; }