设计算法实现将两个递增的带头结点有序链表合并为一个递增的有序链表,要求结果链表仍然使用原来两个链表的存储空间,表中不允许有重复的数据。
时间: 2023-05-30 19:05:38 浏览: 60
算法步骤如下:
1. 定义两个指针p,q分别指向两个链表的首节点(不包含头结点)。
2. 定义一个指针r,指向结果链表的头结点。
3. 如果p和q都不为空,则比较它们的值,将较小的值放入结果链表中,并将指针后移;如果相等,则只将一个值放入结果链表中,并将两个指针都后移。
4. 如果p或q为空,则将另一个链表中剩余的所有节点都放入结果链表中。
5. 返回结果链表的头结点。
算法的时间复杂度为O(n),其中n为两个链表的节点数之和。
代码实现如下:
```
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* p = head1->next;
ListNode* q = head2->next;
ListNode* r = head1;
while (p && q) {
if (p->val < q->val) {
r->next = p;
p = p->next;
} else if (p->val > q->val) {
r->next = q;
q = q->next;
} else {
r->next = p;
p = p->next;
q = q->next;
}
r = r->next;
}
if (p) {
r->next = p;
}
if (q) {
r->next = q;
}
return head1;
}
```