两个单链表求并集、交集、差集(考试最后一道大题、伪代码)c语言

### C语言实现两个单链表的并集、交集和差集 #### 并集操作 为了计算两个有序链表 `A` 和 `B` 的并集，可以创建一个新的链表来存储结果。遍历两个链表并将所有不同的元素依次加入新链表中。 ```c struct ListNode { int val; struct ListNode *next; }; void unionLists(struct ListNode* A, struct ListNode* B, struct ListNode** result) { while (A != NULL && B != NULL) { if (A->val < B->val) { append(result, A->val); A = A->next; } else if (A->val > B->val) { append(result, B->val); B = B->next; } else { append(result, A->val); // or B->val since they are equal A = A->next; B = B->next; } } // Append remaining elements of list A and B while (A != NULL) { append(result, A->val); A = A->next; } while (B != NULL) { append(result, B->val); B = B->next; } } ``` #### 交集操作 对于求解两个升序排列链表 `A` 和 `B` 的交集，可以直接利用双指针法逐一遍历两列表，并仅当两者当前节点值相等时将其添加到目标链表中[^1]。 ```c void intersectionLists(struct ListNode* A, struct ListNode* B, struct ListNode** result) { while (A != NULL && B != NULL) { if (A->val < B->val) { A = A->next; } else if (A->val > B->val) { B = B->next; } else { // 当前结点相同则保存该数值作为公共部分之一 append(result, A->val); A = A->next; B = B->next; } } } ``` #### 差集操作 要获得链表 `A` 减去 `B` 后的结果（即只保留属于 `A` 而不属于 `B` 的那些成员），同样采用双指针策略扫描整个输入数据结构，在遇到重复项时不作处理即可完成此任务。 ```c void differenceLists(struct ListNode* A, struct ListNode* B, struct ListNode** result) { while (A != NULL) { bool found = false; struct ListNode* temp = B; while (temp != NULL) { if (A->val == temp->val) { found = true; break; } temp = temp->next; } if (!found) { append(result, A->val); } A = A->next; } } ``` 上述代码片段展示了如何通过基本逻辑运算符以及简单的控制流语句来构建针对不同集合论概念的具体算法实现方式。值得注意的是，这里假设所有的链表都是按从小到大顺序排序好的；如果不是这种情况，则需要先对其进行预处理以满足条件后再继续后续的操作。