题目内容

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题解

本题是一个经典链表题目，主要思想为双指针算法。

因为两个链表有序，因此双指针算法的应用条件已经成熟，我们有如下思考：

1、链表题，一般都需要虚拟头结点来作为辅助。由于我们不需要在原有链表上进行增删改的操作，因此虚拟头结点用于指向合并后的新链表的头结点，这样我们可以用虚拟头结点用于返回结果，即return dummy->next。

2、定义两个指针，分别指向两个链表的头结点，并开始进行比较。由于虚拟头结点的作用是标记链表的入口，即标记链表的实际头结点，因此虚拟头结点是不可以进行更新和赋值的操作的，所以，我们可以再定义一个尾结点，让尾结点进行合并和更新的操作，所以就可以使用auto tail = dummy。

3、当某个链表遍历完毕之后，如果剩余链表仍然存在未遍历的情况，由于链表有序，那么可以证明剩余链表的各个结点数值一定大于等于合并链表的尾结点的数值，那么将tail的next指针指向剩余链表的开始结点即可。

4、最后返回虚拟头结点的next指针。

代码

/**
 * 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) {
        auto dummy = new ListNode(-1); //定义一个虚拟头结点
        auto tail = dummy; //定义一个新的链表

        while(l1 && l2){
            if(l1 -> val > l2 -> val){
                tail -> next = l2;
                tail = tail -> next;
                l2 = l2 -> next;
            }else{
                tail -> next = l1;
                tail = tail -> next;
                l1 = l1 -> next;
            }
        }
        if(l1){
            tail -> next = l1;
        }
        if(l2){
            tail -> next = l2;
        }
        return dummy -> next;
    }
};