用C语言写一个完整的代码(3)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。
时间: 2024-10-16 17:12:18 浏览: 7
在C语言中,我们可以使用迭代的方式解决这个问题。首先,我们需要定义链表节点结构体和一些辅助函数。以下是实现这个算法的一个完整示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构体
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode;
// 创建新节点
ListNode* createNode(int value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// 比较两个节点并更新结果链表
void mergeLists(ListNode** A, ListNode** B) {
ListNode* currentA = *A, *currentB = *B, *intersection = NULL;
while (currentA && currentB) {
if (currentA->data <= currentB->data) {
// 如果当前A小于等于B,则添加到结果列表
if (!intersection) {
intersection = currentA;
} else {
intersection->next = currentA;
intersection = intersection->next;
}
currentA = currentA->next;
} else {
currentB = currentB->next;
}
}
// 将剩余的部分添加到结果列表
if (currentA) {
*A = currentA;
} else {
*A = NULL;
}
if (currentB) {
*B = currentB;
} else {
*B = NULL;
}
}
// 打印链表
void printList(ListNode* node) {
while (node) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
// 假设我们有以下两个链表(代表集合A和B)
ListNode* listA = createNode(1); // 1 -> 2 -> 3 -> NULL
listA->next = createNode(2);
listA->next->next = createNode(3);
ListNode* listB = createNode(2); // 2 -> 3 -> 4 -> NULL
listB->next = createNode(3);
listB->next->next = createNode(4);
// 初始化结果链表为空
ListNode* result = NULL;
// 计算交集并保存在listA中
mergeLists(&result, &listA);
printf("Intersection of A and B: ");
printList(result);
return 0;
}
```
在这个代码中,`mergeLists` 函数遍历两个链表,将A链表中小于等于B链表中节点的数据添加到结果链表中。最后,我们打印出交集部分。
阅读全文