题目

原题为LeetCode 21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

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

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

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

思路

使用双指针思想解题

• 首先定义两个指针p1，p2分别指向两个有序链表的头结点，定义一个指针p3始终指向新链表的最后一个节点，定义一个指针ptmp指向新链表的头结点。
• 每一次循环都比较两个指针指向节点的值，将偏小的节点加到新链表中（若相等则将p2加到新链表中），且较小的链表上的指针往后移动一位。
• 当p1、p2任意next节点为空时，将非空节点加到新链表中。

图示为：
1.创建链表及指针

2.比较数值大小，把较小的节点加到已排序的链表中

3.将p1指针向后移动

4.将p3移动到已排序链表的最后一个节点

5.同步骤2

6.同步骤3

7.同步骤4

循环执行，直到一方指针为空跳出循环

将非空指针指向的节点加到已排序的链表里，此时返回ptmp->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* list1, ListNode* list2) {
        ListNode* p3=new ListNode(0);
        ListNode* ptmp=p3;

        while(list1 && list2)
        {
            if(list1->val < list2->val)
            {
                p3->next=list1;            
                list1=list1->next;               
            }
            else
            {
                p3->next=list2;               
                list2=list2->next;
            }
            p3=p3->next;
        }
        if(list1)
            p3->next=list1;
        else
            p3->next=list2;
        return ptmp->next;
    }
};

注意事项

注意每一步的执行顺序：将较小节点加入链表->将原链表指针向后移动->将新链表指针向后移动
此处顺序也可以改为：将较小节点加入链表->将新链表指针向后移动->将原链表指针向后移动
这两种顺序本质上并没有区别，但第一种方式实现起来更为优雅

当循环结束后，把原链表非空指针指向的节点加到已排序的链表中即可，返回虚拟头结点的next节点，即可得到合并后的有序链表