用C语言实现:已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。
时间: 2023-05-25 20:03:26 浏览: 129
算法思路:
1. 初始化两个指针p和q分别指向链表A和B的头结点;
2. 循环遍历链表A和B,比较p和q指向结点的值,若相等则将该值存入链表A中,并将p和q都往后移一位;
3. 若p指向结点值小于q指向结点值,则将p往后移一位;
4. 若p指向结点值大于q指向结点值,则将q往后移一位;
5. 循环结束条件为p或q指向结点为空。
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
} Node;
Node* createNode(int value) {
Node* node = (Node*) malloc(sizeof(Node));
node->value = value;
node->next = NULL;
return node;
}
void addNode(Node** head, Node** tail, int value) {
Node* node = createNode(value);
if (*head == NULL) {
*head = *tail = node;
} else {
(*tail)->next = node;
*tail = node;
}
}
void printList(Node* head) {
Node* p = head;
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
printf("\n");
}
void intersect(Node** A, Node* B) {
Node dummy, *tail = &dummy;
while (*A && B) {
if ((*A)->value < B->value) {
*A = (*A)->next;
} else if ((*A)->value > B->value) {
B = B->next;
} else {
tail->next = *A;
tail = *A;
*A = (*A)->next;
B = B->next;
}
}
tail->next = NULL;
}
int main() {
Node *A = NULL, *B = NULL;
Node *tail1, *tail2;
addNode(&A, &tail1, 1);
addNode(&A, &tail1, 3);
addNode(&A, &tail1, 5);
addNode(&A, &tail1, 7);
addNode(&B, &tail2, 2);
addNode(&B, &tail2, 4);
addNode(&B, &tail2, 5);
addNode(&B, &tail2, 8);
printf("A: ");
printList(A);
printf("B: ");
printList(B);
intersect(&A, B);
printf("A intersect B: ");
printList(A);
return 0;
}
```
运行结果:
```
A: 1 3 5 7
B: 2 4 5 8
A intersect B: 5
```