3、A、B为元素递增有序排列的单链表(同一表中可能有相同元素),编写算法另建一单链表C,保存两个表的公共元素,要求C的元素值各不相同且递增有序。
时间: 2024-02-15 14:06:18 浏览: 19
算法思路:
1. 首先定义三个指针,p1指向链表A的头结点,p2指向链表B的头结点,p3指向链表C的头结点(初始化为空)。
2. 然后开始遍历链表A和链表B,比较p1和p2指向的节点的值大小,如果p1指向的节点的值小于p2指向的节点的值,那么p1向后移动一位;如果p1指向的节点的值大于p2指向的节点的值,那么p2向后移动一位;如果p1指向的节点的值等于p2指向的节点的值,那么将该节点插入到链表C中,并将p1和p2同时向后移动一位。
3. 最后返回链表C即可。
算法实现:
```
ListNode* getCommonList(ListNode* headA, ListNode* headB) {
ListNode* p1 = headA;
ListNode* p2 = headB;
ListNode* p3 = NULL;
ListNode* tail = NULL;
while (p1 && p2) {
if (p1->val < p2->val) {
p1 = p1->next;
} else if (p1->val > p2->val) {
p2 = p2->next;
} else {
ListNode* node = new ListNode(p1->val);
if (p3 == NULL) {
p3 = node;
tail = node;
} else {
tail->next = node;
tail = tail->next;
}
p1 = p1->next;
p2 = p2->next;
}
}
return p3;
}
```