系列文章目录
文章目录
前言
每天进步一点点呀！！
一、背景
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1：
输入：L1 = [1,2,4], L2 = [1,3,4]
输出：[1,1,2,3,4,4]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
二、我的思路
之前做过一个关于“两个链表做加法”的题目，其实两者很类似。
这个题目核心就是说，链表是升序，那么合并的话，就遍历链表，一个个去比较，再是选取小的，形成新的链表。当一个链表空了，那么只需将不空的链表合在新链表的后面。
代码如下：
/**
* 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* l1, ListNode* l2) {
ListNode* myList=new ListNode(0,NULL);
ListNode* r=myList;//干脆创建一个有结点的值
ListNode *p=l1;
ListNode *q=l2;
while(p!=NULL||q!=NULL)
{
if(p==NULL)
{
r->next=q;
return myList->next;
}
else if(q==NULL)
{
r->next=p;
return myList->next;
}
ListNode* node=new ListNode;
if ( p->val <= q->val )
{
node->val = p->val;
p=p->next;
}
else
{
node->val = q->val;
q=q->next;
}
node->next=NULL;
r->next=node;
r=node;
}
return myList->next;
}
};
注意，我这里的while循环是当两个链表为空才结束，然后内置判空的操作再退出循环。这主要是考虑之前做的那个链表求和的题目（两数相加，好像是），学的一个技巧，发现用在这里没有取巧的感觉。
所以，只需当一个为空就可以停止循环了。
三、官方的思路
技巧：无需创建新的链表，只需返回一个索引就可，即表明各结点之间的先后关系即可。
其实我的代码是矛盾的，本来我是想建立一个新的链表的，但是当某一个链表空了的时候，我就直接不新建节点了，而只给了一个索引关系。
且看官方的代码：
1、迭代
这个是迭代的办法，时间复杂度：O(n + m)，空间复杂度：O(1)。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
2、递归
由于比较过程是一致的，所以用递归完成这个比较的过程，每次把未完成的结点传递下去即可，然后给出一个递归出口。
官方给了一个递归的方法：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
时间复杂度和空间复杂度都是：O(n + m)。
总结
思路清晰，不难想的。
哦，对对对，还有一个链表方面的问题，我写代码的时候很纠结。就是要返回头指针嘛，这个时候创建的话，又不能把第一个元素放在这个头指针里面，形成无头指针，那么这个时候就只能有头指针了。给这个头指针放一个任意值，然后把head->next作为函数返回值。
ListNode* myList=new ListNode(0,NULL);
喜欢就点个赞叭！！