原题

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

示例：

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

链表结构如下

   let l1 = {
      val: 3,

      next: null,
    };
    let l2 = {
      val: 1,

      next: {
        val: 2,

        next: {
          val: 4,

          next: null,
        },
      },
    };

解法1

这道题着实让我摇摆许久，感觉智商有些不够用，缝缝补补勉强通过测试的解决方案如下：

    var mergeTwoLists = function(l1, l2) {
      if (l1 === null) return l2;
      if (l2 === null) return l1;
      let next = l1.next,
        lastNode = null,
        result = l1;
      while (l2 != null) {
        if (l2.val >= l1.val) {
          //向后插入
          if (next === null) {
            l1.next = l2;
            break;
          } else if (l2.val < next.val) {
            l1.next = l2;
            l2 = l2.next;
            l1.next.next = next;
          }
          lastNode = l1;
          l1 = l1.next;
          next = l1.next;
        } else {
          //向前插入
          if (lastNode === null) {
            let l2Next = l2.next;
            l2.next = l1;
            result = l2;
            l2 = l2Next;

            l1 = result;
            next = l1.next;
          } else {
            lastNode.next = l2;
            l2 = l2.next;
            lastNode.next.next = l1;
          }
        }
      }
      return result;
    };

虽然用我的膝盖骨也能感觉出这种解法是比较low的，但是我又没有办法!
用l1作为目标链表，遍历l2，因为l1和l2 都会迭代自身，所以result = l1;保存了最初的引用，这很重要。
程序在向前插入和向后插入两个基本情况下，分出前后节点是否为null的子情况，因此只要填充完这四种情况算法就完成了

1

当if (next === null) {成立，说明l1比较到最后一个节点，l2后面若还有节点的都会比l1大，直接拼接，l2没有节点这种写法也没问题，so easy!
比如:l1 = [1]和l2 = [2,3,4,5]

2

当else if (l2.val < next.val) { 成立，说明 l2的第一个节点需要放在l1第一个节点和第二个节点中间，
这时候代码的顺序是很关键的，比如l1 = [1,5]和l2 = [2]
l1.next = l2; l1第一个节点链接l2，
l2 = l2.next; 向下遍历l2，此时 l1第一个节点链接就是旧 l2的第一个节点,
l1.next.next = next;旧 l2的第一个节点链接l1第二个节点。
确实很绕是不是，我快哭了！

最后更新lastNode、l1、next，这里隐去了 l2的第一个节点大于l1第二个节的情况，都是更新这三个值

但是写文章的时候发现，因为是有序数组，当发生向后插入时，便不会再出现向前插入的情况，所以不用更新lastNode， lastNode = l1; 没有任何意义

3

当if (lastNode === null) { 成立时，这里我被坑了两次，此时相当于像result的最前面插入，lastNode不用更新
let l2Next = l2.next; 先存储l2的下一个节点
l2.next = l1; 将l2第一个节点放在l1第一个节点前面，注意result = l1;曾保存初始引用，接下来必然要更新result = l2; 否则result上体现不了这一次改变
l2 = l2Next; 向下迭代l2
l1 = result;next = l1.next; 再一次比较还是新插入的元素，
以l1 = [5]和l2 = [1，2]为例，将1放入5前面后，2还是小于5，如果下次比较还是5，则出现了向前插入的情况，需要记录lastNode，不如不记录使其复用情况1和情况2

4

写文章的时候发现，基于情况2、3的论证，情况4是不会被执行的，当发生一次if (lastNode === null) { 后，因为是有序数组，后续只会出现情况1和2
最终代码如下

var mergeTwoLists = function(l1, l2) {
      if (l1 === null) return l2;
      if (l2 === null) return l1;
      let next = l1.next,
        lastNode = null,
        result = l1;
      while (l2 != null) {
        if (l2.val >= l1.val) {
          //向后插入
          if (next === null) {
            l1.next = l2;
            break;
          } else if (l2.val < next.val) {
            l1.next = l2;
            l2 = l2.next;
            l1.next.next = next;
          }

          
          l1 = l1.next;

          next = l1.next;
        } else {
          //向前插入
          if (lastNode === null) {
            let l2Next = l2.next;
            l2.next = l1;
            result = l2;
            l2 = l2Next;

            l1 = result;
            next = l1.next;
          }
        }
      }
      return result;
    }

如果能统一思想，保证l2的所有节点都是在l1后插入，代码就更简洁了
做题的时候，有序二字未能够引起足够的重视！

解法2