数据结构007：合并两个有序链表
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
示例 1
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
题解
根据题意我们首先能想到的是依次遍历list1和list2，并判断其val的大小，小的接入我们新合成的链表，并将小的链表指针往后更新一位，再继续比较当前两个链表第一个元素的大小。具体的实现思路如下：首先声明一个新的节点prenode和一个指向该节点的指针head，判断list1->val和list2->val的大小，如果list1->val < list2->val，则prenode.next = list1，并将list1更新为list1->next，将指针head更新为head->next，然后继续比较list1->val和list2->val的大小，直至list1或者list2变为nullptr，然后将head->next指向剩余非空的list。具体的代码实现如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode prenode(-1);
ListNode* head = &prenode;
while(list1 != nullptr && list2 !=nullptr){
if(list1->val < list2->val)
{
head->next = list1;
list1 = list1->next;
}else{
head->next = list2;
list2 = list2->next;
}
head = head->next;
}
head->next = list1==nullptr ? list2 : list1;
return prenode.next;
}
};
时间复杂度O(m+n) ，其中m、n 分别为list1和list2的长度。空间上，只是用了有限个变量，因此空间复杂度为O(1) 。
其实在解决链表相关的问题的时候，递归也是一种常用的解决方法，递归就是函数不断的调用自己，直到结束条件为止，然后进行回溯，最终的得到答案。因此使用递归的方法需要确定两个问题：
- 结束条件
- 如何递归
在本题目中，递归的结束条件应为当list1或list2有一个为空的时候，在不满足上述条件的时候，应该不断地判断当前list1->val和list2->val的大小，然后使用较小list->next与另外一个list作为参数，调用递归函数本身。具体的代码实现如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr)return list2;
if(list2 == nullptr)return list1;
if(list1->val < list2->val){
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
时间复杂度O(m+n) ，其中m、n 分别为list1和list2的长度。空间上，由于一般情况下需要迭代m+n 次，使用了 m+n 个栈帧，因此空间复杂度为O(m+n) 。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-12-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
