【算法专题--链表】合并两个有序链表--高频面试题（图文详解，小白一看就会！！）

目录

一、前言

二、题目描述 

 三、解题方法

 ⭐迭代法 --- 带哨兵位（头节点）

 ⭐递归法

 四、总结与提炼

 五、共勉

一、前言

        合并两个有序链表这道题，可以说是--链表专题--，比较经典的一道题，也是在面试中频率较高的一道题目，通常在面试中，面试官可能会要求我们写出多种解法来实现这道题目，所以大家需要对这道题目非常熟悉哦！！
        本片博客就来详细的讲讲解一下 合并两个有序链表 的多种实现方法，让我们的面试变的更加顺利！！！

二、题目描述 

 题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

 三、解题方法

 ⭐迭代法 --- 带哨兵位（头节点）

 首先，先来了解一下什么是  哨兵位---头节点 ？

• 它是一个附加的链表结点，该 结点 作为第一个节点，它的数据域不存储任何东西，只是为了操作的方便而引入的。
• 也就是说，如果一个链表有哨兵节点的话，那么链表表的第一个元素应该是链表的第二个节点。 

 哨兵位---头节点的作用：

•  比如向链表中插入一个节点，对于没有哨兵位的单链表，当待插入的节点为链表的第一个节点，由于没有前驱，需要进行特殊处理，从而代码的复杂性增加。
• 如果有哨兵位头节点，则第一个节点的处理方式与其它节点相同，可以统一进行处理。

 解题思路：

•  首先设置一个新的节点 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;
        }
    } 
};

 四、总结与提炼

      最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关链表合并的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握

 五、共勉

      以下就是我对 合并有序链表 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！