题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
具体如下图：
即，将 L1 和 L2 链表进行合并。
思路1：递归
每次比较 l1 和 val 和 l2 的 val，谁小，就继续循环他的 next 节递归进行比较，且返回值作为小节点的 next。
终止条件，就是 l1 为 null 或者 l2 为 null，任意一者为 null，都应当返回另一者（肯定不为 null，且有序）。
算法空间复杂度和时间复杂度都是 O（n+m）；
图示：
代码如下：
static public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
// 如果 l2 比 l1 大, 那 l1 的 next 就是 返回值(升序).
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
思路 2：循环
刚刚上面说了，每次都是比较 L1 的 val 和 L2 的 val，谁小，就继续拿小节点的 next 节点和当前节点比较。
这个思路也可以用在循环中。
代码如下：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
if (l1 == null) {
pre.next = l2;
} else {
pre.next = l1;
}
return dummy.next;
}
我们在循环中，每次比较 L1 的值和 L2 的值，谁小，就更新谁的指针——继续比较他的 next。
同时，我们定义一个虚拟节点，用于保存合并后的链表指针。
用一个 pre 节点，保存迭代的前指针。目的是让前指针保存经过排序的 节点。
最后，如果出现了 null 值，就将非 null 值链接到表尾。
返回虚拟节点的 next，就是排序后的数据。
算法空间复杂度 O1，时间复杂度 O（n + m）；
总结
该题的解法关键在于：每次循环或递归，都应当找到两个节点中，较小的那个，然后继续比较较小的那个 next 节点。
