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

    1. /**
    2.  * 递归
    3.  * 时间复杂度：O(n+n)
    4.  * 空间复杂度：O(n+m)
    5.  */
    6. var mergeTwoLists1 = function (l1, l2) {
    7.   if (!l1) return l2
    8.   if (!l2) return l1
    9.   if (l1.val < l2.val) {
    10.     l1.next = mergeTwoLists(l1.next, l2)
    11.     return l1
    12.   } else {
    13.     l2.next = mergeTwoLists(l1, l2.next)
    14.     return l2
    15.   }
    16. }
    1. /**
    2.  * 迭代
    3.  * 时间复杂度：O(n+n)
    4.  * 空间复杂度：O(1)
    5.  */
    6. var mergeTwoLists = function (l1, l2) {
    7.     const pre = new ListNode(null)
    8.     let curr = pre
    9.     while (l1 && l2) {
    10.         if (l1.val <= l2.val) {
    11.             curr.next = l1
    12.             l1 = l1.next
    13.         } else {
    14.             curr.next = l2
    15.             l2 = l2.next
    16.         }
    17.         curr = curr.next
    18.     }
    19.     curr.next = l1 || l2
    20.     return pre.next
    21. }