题目入口📌：合并两个有序链表
问题描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入输出示例：
解题分析
合并链表跟合并数组差不多，合并两个数组，是分别比较两个数组中元素的大小，然后放入新数组中。对于链表来说，我们不需要准备新的链表，我们可以直接在原有链表的基础上进行修改。
对我们来说，合并链表后的头结点难以确定，如果 链表list1 的头结点 小于 链表list2的头结点，那么合并后的链表的 头结点就是 list1的头结点，反之就是 list2的头结点。这样判断头结点，有点过于复杂，我们可以新开辟一个傀儡结点（虚拟节点）newHead，然后 newHead 的val值赋为-1，同时创建一个 tmp指针指向newHead 结点。
这样我们就可以省去头结点的确认，因为newHead.next 就是合并后链表的头结点。
tmp: 便于我们合并链表
接下来就是合并list1 和 list2 两个链表了，不断比较 list1 和 list2 所指向结点的val 值大小
如下图，list1.val 小于 list2.val，所以便把 list1 的地址传给 tmp.next，list1和tmp都向后移一步，list2保持不动。当list1.val 大于 list2.val，具体操作类似。
在判断两个链表是个多次的比较过程，所以我们要放到循环里面，那循环结束的条件我们还没确定。如下图，当 list2 指向null时，我们就要结束比较了，因为在比较下去编译器就会报出空指针异常。
所以一这段的代码我们可以写为：
while(list1 != null && list2 != null){ if(list1.val < list2.val){ tmp.next = list1; list1 = list1.next; tmp = tmp.next; }else{ tmp.next = list2; list2 = list2.next; tmp = tmp.next; } }
当 list1 或 list2 指向null时，我们的合并工作就会变得轻松很多。如下图，list2 指向 null，我们就可以直接把 list1 剩余部分加到 tmp 后面。
tmp.next = list1;
因为两个链表都是有序的，当一个链表没有结点可以合并时，就可以把另一个链表的剩余部分直接加到合并链表的末尾。
代码实现
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode newHead = new ListNode(-1); ListNode tmp = newHead; while(list1 != null && list2 != null){ if(list1.val < list2.val){ tmp.next = list1; list1 = list1.next; tmp = tmp.next; }else{ tmp.next = list2; list2 = list2.next; tmp = tmp.next; } } if(list1 != null){ tmp.next = list1; } if(list2 != null){ tmp.next = list2; } return newHead.next; } }
