文章目录
- 碎碎念
- 一、题目
- 二、思路和题解
-
- 1.思路
- 2.代码
- 三、其他解法
-
- 1.迭代
- 2.递归
- 四、错误回顾
碎碎念
加油！没问题！就这样保持状态！很好！
一、题目
二、思路和题解
1.思路
这里我就没有想的太复杂了，直接就是按照题目的意思一步一步来。先考虑特殊情况：如果有其中一个链表是空，那返回另一个就可以了（两个链表都是空的情况也是包含在内的）。再是一般情况，准备两个指针分别指向两个链表的头节点，每一步都比较大小，小的就放到新创建的链表新创建的节点里，然后这一条链上的指针往后移，再比大小，看把谁的值放进合并链表的新节点里，以此类推。
这个循环的终止条件是当其中一个链表的节点已经遍历完了走到最后了，这时候就出循环。由于两个链表都是非降序排列的，此时我们将另一个链表多出来的这一节拼到我们的合并链表后即可。
2.代码
/**
* 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;
}
//定义两个指针方便取数比大小，不过为了让代码更简洁一些可以直接用list1和list2，后面会给出简化一点的代码
ListNode* ptr1=list1;
ListNode* ptr2=list2;
//新链表的第一个节点
ListNode* res=new ListNode();
ListNode* head=res;//头指针
//先比较第一个节点的数，谁小就谁放在新的节点里
if (ptr1->val <= ptr2->val){
res->val=ptr1->val;
ptr1=ptr1->next;
}else{
res->val=ptr2->val;
ptr2=ptr2->next;
}
//当某一个链表遍历完了就结束循环
while (ptr1!=nullptr&&ptr2!=nullptr){
ListNode* newnode=new ListNode();
res->next=newnode;
if (ptr1->val <= ptr2->val){
newnode->val=ptr1->val;
ptr1=ptr1->next;
}else{
newnode->val=ptr2->val;
ptr2=ptr2->next;
}
res=res->next;
}
//判断一下到底是哪条链表已经遍历完了，便于选择另一条链表接着拼
if (ptr1==nullptr){
while(ptr2!=nullptr){
ListNode* newnode=new ListNode();
res->next=newnode;
newnode->val=ptr2->val;
res=res->next;
ptr2=ptr2->next;
}
}else{
while(ptr1!=nullptr){
ListNode* newnode=new ListNode();
res->next=newnode;
newnode->val=ptr1->val;
res=res->next;
ptr1=ptr1->next;
}
}
return head;
}
};
三、其他解法
原题解在这里。
1.迭代
和上面的思路是差不多的，但是不需要新开辟空间建链表，只需要改变指针指向把两个链表合并在一起就可以了。可以去原题解看看动态演示~
算法： 首先，我们设定一个哨兵节点 prehead ，方便最后我们返回合并后的链表。然后我们用 prev 指针来拼接两个链表，我们需要做的是调整它的 next 指针。我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。
在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
代码：
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;
}
};
2.递归
可以把这个合并的过程定义成下面这个递归式（看的时候好看懂但还是想感叹一句好聪明啊怎么想出来的）：
m
e
r
g
e
(
l
i
s
t
1
,
l
i
s
t
2
)
=
{
l
i
s
t
1
[
0
]
+
m
e
r
g
e
(
l
i
s
t
1
[
1
:
]
,
l
i
s
t
2
)
l
i
s
t
1
[
0
]
<
l
i
s
t
2
[
0
]
l
i
s
t
2
[
0
]
+
m
e
r
g
e
(
l
i
s
t
1
,
l
i
s
t
2
[
1
:
]
)
o
t
h
e
r
w
i
s
e
merge(list1,list2)=\\left\\{\\begin{matrix} list1[0]+merge(list1[1:],list2) & list1[0]<list2[0]\\\\ list2[0]+merge(list1,list2[1:]) & otherwise \\end{matrix}\\right.
merge(list1,list2)={list1[0]+merge(list1[1:],list2)list2[0]+merge(list1,list2[1:])list1[0]<list2[0]otherwise 算法： 如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束（边界条件）。
代码：
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;
}
}
};
四、错误回顾
这次做题发现自己有些东西忘得一干二净了简直…来补课！
用new创建链表节点并插入：
Listnode *newnode = new Listnode(val);
cur -> next = newnode;
cur = cur -> next;
(有笨蛋写成new(ListNode)…)
