一、题目描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的结点仍然是递增排序的。
要求：空间复杂度 O(1)，时间复杂度 O(n)。
二、题目解析
1、一开始设置一个虚拟结点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值。
2、设置一个指针 pre，指向虚拟结点，在后续的操作过程中，会移动 pre 的位置，让它指向所有已经排好序的结点里面的最后一个结点位置。
3、借助 while 循环，不断的比较 list1 和 list2 中当前结点值的大小，直到 list1 或者 list2 遍历完毕为止。
4、在比较过程中，如果 list1 当前结点的值小于等于了 list2 当前结点的值，让 pre 指向结点的 next 指针指向这个更小值的结点，即 list1 上面的当前结点，同时继续访问 list1 的后续结点。
5、如果 list1 当前结点的值大于了 list2 当前结点的值，让 pre 指向结点的 next 指针指向这个更小值的结点，即 list2 上面的当前结点，同时继续访问 list2 的后续结点。
6、每次经过 4 、5 的操作之后，都会让 pre 向后移动，因为需要保证 pre 指向所有已经排好序的结点里面的最后一个结点位置。
三、参考代码
// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
public class Solution {
public ListNode Merge(ListNode list1, ListNode list2) {
// 一开始设置一个虚拟结点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
ListNode dummy = new ListNode(-1);
// 设置一个指针，指向虚拟结点
ListNode pre = dummy;
// 通过一个循环，不断的比较 list1 和 list2 中当前结点值的大小，直到 list1 或者 list2 遍历完毕为止
while (list1 != null && list2 != null) {
// 如果 list1 当前结点的值小于等于了 list2 当前结点的值
if (list1.val <= list2.val) {
// 让 pre 指向结点的 next 指针指向这个更小值的结点
// 即指向 list1
pre.next = list1;
// 让 list1 向后移动
list1 = list1.next;
} else {
// 让 pre 指向结点的 next 指针指向这个更小值的结点
// 即指向 list2
pre.next = list2;
// 让 list2 向后移动
list2 = list2.next;
}
// 让 pre 向后移动
pre = pre.next;
}
// 跳出循环后，list1 或者 list2 中可能有剩余的结点没有被观察过
// 直接把剩下的结点加入到 pre 的 next 指针位置
// 如果 list1 中还有结点
if (list1 != null) {
// 把 list1 中剩下的结点全部加入到 pre 的 next 指针位置
pre.next = list1;
}
// 如果 list2 中还有结点
if (list2 != null) {
// 把 list2 中剩下的结点全部加入到 pre 的 next 指针位置
pre.next = list2;
}
// 最后返回虚拟结点的 next 指针
return dummy.next;
}
}
