A、B为元素递增有序排列的单链表(同一表中可能有相同元素),编写算法另建一单链表C,保存两个表的公共元素,要求C的元素值各不相同且递增有序。
时间: 2023-06-19 13:05:16 浏览: 49
可以使用双指针的方法来实现这个算法,具体步骤如下:
1. 定义两个指针p1和p2,分别指向链表A和B的头节点。
2. 定义一个指针p3,指向链表C的头节点,初始化为空。
3. 当p1和p2都不为空时,比较它们所指向的节点的值:
- 如果节点A的值小于节点B的值,则p1向后移动一位。
- 如果节点A的值大于节点B的值,则p2向后移动一位。
- 如果节点A的值等于节点B的值,则将该值插入到链表C中,然后p1和p2都向后移动一位。
4. 最后返回链表C。
以下是具体的实现代码(假设链表节点的结构体定义如下):
```c
struct ListNode {
int val;
struct ListNode *next;
};
```
```c
struct ListNode* getIntersection(struct ListNode* headA, struct ListNode* headB) {
struct ListNode *p1 = headA, *p2 = headB, *p3 = NULL, *tail = NULL;
while (p1 && p2) {
if (p1->val < p2->val) {
p1 = p1->next;
} else if (p1->val > p2->val) {
p2 = p2->next;
} else {
struct ListNode *node = malloc(sizeof(struct ListNode));
node->val = p1->val;
node->next = NULL;
if (tail) {
tail->next = node;
} else {
p3 = node;
}
tail = node;
p1 = p1->next;
p2 = p2->next;
}
}
return p3;
}
```