合并两个有序链表【LC21】
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题解【迭代】
当list1和list2都不是空链表时，判断list1和list2哪一个链表的头节点的值更小，将较小值的节点添加到结果里，并将对应链表的节点后移一位，另一个链表不动，在下一个循环继续进行比较，则最后list1和list2最多有一个是非空的，并且输入链表为递增链表，所有最后再将剩余非空链表拼接在合并链表的后面，并返回即可。
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(-1); ListNode prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev.next = l1 == null ? l2 : l1; return prehead.next; } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析
时间复杂度：O(N+M)，其中 N和M分别是链表中的节点数。
空间复杂度：O(1)
题解【递归】
终止条件：当两个链表都为空时，表示我们对链表已合并完成。
如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度分析
- 时间复杂度：O(N+M)，其中 N和M分别是链表中的节点数。
- 空间复杂度：O(N+M)
