两个有序链表序列的合并
时间: 2023-09-15 08:20:35 浏览: 108
题目描述:
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
解题思路:
这道题可以使用递归和迭代两种方法来解决。
递归方法:
首先,如果两个链表中有一个是空链表,那么直接返回另一个链表即可。如果两个链表都不为空,则比较两个链表的头节点,将较小的那个节点作为合并后链表的头节点,并递归地将较小节点的 next 与另一个链表的头节点继续合并。最后返回合并后的链表头节点即可。
迭代方法:
首先,需要定义一个哑节点 dummy,用来表示合并后的链表的头节点。然后,定义一个指针 p,初始时指向 dummy 节点。接着,比较两个链表的头节点,将较小的那个节点插入到 p 的后面,并将 p 向后移动一位。最后,将较小节点所在的链表的头节点向后移动一位,并继续进行比较和插入操作,直到一个链表为空。最后,将另一个链表的剩余节点插入到合并后的链表的尾部,返回 dummy.next 即可。
代码实现:
递归方法:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
迭代方法:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
}
else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if (l1) p->next = l1;
if (l2) p->next = l2;
return dummy->next;
}
};