给定两个链表,每个链表都已经按升序排列,设计算法实现将两个链表合并到一个升序链表中,返回合并后的链表。 输入样例: 1 4 5 1 3 6 输出样例: 1 1 3 4 5 6
时间: 2023-05-28 12:03:00 浏览: 46
算法思路:
新建一个链表作为合并后的链表,同时设置两个指针分别指向两个原始链表的头节点。
比较两个指针所指节点的值,将较小值的节点加入到合并后的链表中,并将指针后移一位。
当两个链表中有一个为空时,将另一个链表剩余部分直接加入到合并后的链表中。
返回合并后的链表头节点。
代码实现:
C++ 代码
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
Python 代码
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
dummy = ListNode(-1)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next