目录
一、前言
合并两个有序链表这道题，可以说是--链表专题--，比较经典的一道题，也是在面试中频率较高的一道题目，通常在面试中，面试官可能会要求我们写出多种解法来实现这道题目，所以大家需要对这道题目非常熟悉哦！！
本片博客就来详细的讲讲解一下 合并两个有序链表 的多种实现方法，让我们的面试变的更加顺利！！！
二、题目描述
三、解题方法
⭐迭代法 --- 带哨兵位（头节点）
首先，先来了解一下什么是 哨兵位---头节点 ？
- 它是一个附加的链表结点，该 结点 作为第一个节点，它的数据域不存储任何东西，只是为了操作的方便而引入的。
- 也就是说，如果一个链表有哨兵节点的话，那么链表表的第一个元素应该是链表的第二个节点。
哨兵位---头节点的作用：
- 比如向链表中插入一个节点，对于没有哨兵位的单链表，当待插入的节点为链表的第一个节点，由于没有前驱，需要进行特殊处理，从而代码的复杂性增加。
- 如果有哨兵位头节点，则第一个节点的处理方式与其它节点相同，可以统一进行处理。
解题思路：
- 首先设置一个新的节点 pre_head (哨兵节点) 赋值为-1（默认为无数据存在）
- 其次，需要维护一个 cur 指针，即 调整 它的 next指针（cur->next），确保它指向当前新链表 值 较小的节点，初始 cur = pre_head
- 取两个链表的头节点，存放在 list1 和 list2 ,然后重复操作：如果 list1 所在的节点值 小于 list2 所在节点的值，我们就把 list1 当前的节点接在 cur 节点的后面，同时将 list1 指针向后移。否则 对 list2 做同样的操作。然后将 cur 指针后移一位。
- 当其中一条链表终止的时候， list1 和 list2 至多有一个是非空的。由于两个链表都是有序的，所以无论那个链表非空，它剩下部分包含的所有元素都比前面已经 合并链表中的所有元素都要大。所以我们只需要将非空链表接在合并链表的后面，并返回合并链表。
图例： list1: 1 , 2, 4 list2: 3 ,5 , 6
代码：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
// 创建一个新的链表 ，并初始化头节点 为-1 ---- 这是一个 哨兵位
// 哨兵位，不存储数据
ListNode* pre_head = new ListNode(-1);
// 维护一个 cur 指针，指向当前较小的节点
ListNode* cur = pre_head;
// 注意巧妙的利用 哨兵位的头节点
while(list1!=nullptr && list2!=nullptr)
{
// 将较小的节点进行 尾插
if(list1->val < list2->val)
{
cur->next = list1;
list1 = list1->next;
}
else
{
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
// 判断谁没结束，将它直接连接在 cur->next上
if(list1!=nullptr)
{
cur->next = list1;
}
else
{
cur->next = list2;
}
// 注意返回 链表的头节点，而不是 哨兵节点
return pre_head->next;
}
};⭐递归法
解题思路：
我们记两个链表的头节点分别为 list1 和 list2，在 合并两个链表 的时候会遇到以下三种情况：
list1为空，直接返回list2；list2为空，直接返回list1;
两节点都不为空，那么又会分为两种情况:
- list1 节点值小于 list2 节点值，那么 list1 节点将会是合并后的节点新的头节点，剩下的部分是 list1->next 和 list2 合并的节点，而合并 list1->next 和 list2 是合并 list1 和 list2 的子问题，也可以使用 mergeTwoLists 函数来解答，于是有 list1->next = mergeTwoLists(list1->next, list2)，并返回 list1；
- 同理，
list2节点值小于list1节点值时，有list2->next = mergeTwoLists(list1, list2->next)，并返回list1。
以上这种将问题转换为原问题的子问题的方法，称为递归方法。递归方法是一种边调用边填充的方法。
代码：
/**
* 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;
}
else if (list2 == nullptr) {
return list1;
}
else if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
四、总结与提炼
最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关链表合并的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握
五、共勉
以下就是我对 合并有序链表 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！
