难度：简单

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

    示例：

    1. 输入：1->2->4, 1->3->4
    2. 输出：1->1->2->3->4->4

    思路分析：
    使用递归实现，新链表也不需要构造新节点，我们下面列举递归三个要素

    • 终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
    • 返回值：每一层调用都返回排序好的链表头
    • 本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理

    代码实现：

    1. var mergeTwoLists = function(l1, l2) {
    2.         if (l1 == null) {
    3.         return l2;
    4.     }
    5.     if (l2 == null) {
    6.         return l1;
    7.     }
    9.     let tempObj = {};
    10.     if (l1.val <= l2.val) {
    11.         tempObj = l1;
    12.         tempObj.next = mergeTwoLists(l1.next, l2);
    13.     } else {
    14.         tempObj = l2;
    15.         tempObj.next = mergeTwoLists(l2.next, l1);
    16.     }
    18.     return tempObj;
    19. };

    双指针

    1. let mergeTwoLists = (l1, l2) => {
    2.     let head = new ListNode(), pre = head
    3.     while (l1 && l2) {
    4.         if(l1.val > l2.val){
    5.             pre.next = l2
    6.             l2 = l2.next
    7.         } else {
    8.             pre.next = l1
    9.             l1 = l1.next
    10.         }
    11.         pre = pre.next
    12.     }
    13.     pre.next = l1 ? l1 :l2
    14.     return head.next
    15. };