1.题目

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

示例 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 均按 非递减顺序 排列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists

2.思路

（1）双指针
该思路与归并排序中归并两个序列的思想类似，只不过本题将序列换成了链表，具体思路如下：
① 定义虚拟头结点 dummy，以及结点 p = dummy；
② 定义双指针 p1 和 p2 ，它们初始时分别指向题中的两个升序链表；
③ 开始遍历这两个升序链表（直到其中一个遍历完为止），比较 p1.val 和 p2.val，将值较小的结点连接到p的后面，并且分别向后移动相应的指针；
④ 遍历结束后分别处理两个链表中的剩余部分（最多只有一个有剩余），即直接将其分别连接到 p 的后面，最后返回dummy.next即可。

3.代码实现（Java）

//思路1————双指针
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //定义虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = list1, p2 = list2;
        while (p1 != null && p2 != null) {
        	//比较p1.val和p2.val，将值较小的结点连接到p的后面
            if (p1.val > p2.val) {
                p.next = p2;
                //p2向后移动
                p2 = p2.next;
            } else {
                p.next = p1;
                //p1向后移动
                p1 = p1.next;
            }
            //p向后移动
            p = p.next;
        }
        //将剩余部分直接连接到p的后面
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }
}