将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
时间: 2023-03-31 13:02:22 浏览: 61
可以使用双指针法,依次比较两个链表的节点大小,将较小的节点接在结果链表的末尾。最后将剩余的节点直接接在结果链表的末尾即可。具体实现可以参考以下代码:
void merge(ListNode* l1, ListNode* l2) {
ListNode* p1 = l1;
ListNode* p2 = l2;
ListNode* tail = NULL;
while (p1 && p2) {
if (p1->val < p2->val) {
if (!tail) {
tail = p1;
l1 = tail;
} else {
tail->next = p1;
tail = tail->next;
}
p1 = p1->next;
} else {
if (!tail) {
tail = p2;
l1 = tail;
} else {
tail->next = p2;
tail = tail->next;
}
p2 = p2->next;
}
}
if (p1) {
tail->next = p1;
}
if (p2) {
tail->next = p2;
}
}
阅读全文