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

一、前言

二、题目描述

三、解题方法

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

⭐递归法

四、总结与提炼

五、共勉

一、前言

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

二、题目描述

题目链接：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;
        }
    } 
};