Day275:输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

[Genzhen]

每日一题会在下午四点在交流群集中讨论，五点小程序中更新答案 欢迎大家在下方发表自己的优质见解

二维码加载失败可点击 小程序二维码

扫描下方二维码，收藏关注，及时获取答案以及详细解析，同时可解锁800+道前端面试题。

---

思路分析

做链表类的处理，我们要把握住一个中心思想：处理链表的本质，是处理链表结点之间的指针关系

这道题也不例外，我们来看下处理前两个链表的情况。

两个链表如果想要合并为一个链表，我们恰当地补齐双方之间结点 next 指针的指向关系，就能达到目的。

如果这么说还是感觉抽象，那么不妨把上图中的六个结点想象成为 6 个扣子：现在的情况是六个扣子被分成了两拨，各自有一根线把它们穿了起来。我们现在的目的就是让这六个扣子按照一定的顺序，穿到一根线上去。我们要做的就是一个穿针引线的活，现在线有了，缺的是一根针。

这根针每次钻进扣子眼儿之前，要先比较一下它眼前的两个扣子，选择其中值较小的那个，优先把它串进去。一次串一个，直到所有的扣子都被串进一条线为止（下图中红色箭头表明穿针的过程与方向）：

另外还需要注意的是，两个链表存在不等长的情况，如果其中一个链表已经完全被串进新链表里，而另一个链表还有剩余结点，考虑到本身链表是有序的，所以我们可以把它整个拼到目标链表的尾部。

参考实现

function ListNode(val) {
  this.val = val;
  this.next = null;
}
/**
 * @param {ListCode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoList = function (l1, l2) {
  // 定义头结点，确保列表可以被访问到
  let head = new ListNode();
  // 需要的那根针
  let cur = head;
  // 开始在两个链表之间穿梭
  while (l1 && l2) {
    // 如果l1的结点值比较小
    if (l1.val <= l2.val) {
      // 先串起l1的结点
      cur.next = l1;
      // l1 指针向前一步
      l1 = l1.next;
    } else {
      // l2 较小时，先串起l2 结点
      cur.next = l2;
      // l2 向前一步
      l2 = l2.next;
    }
    // 针在串起一个节点之后，也会往前一步
    cur = cur.next;
  }
  // 处理链表不等长的情况
  cur.next = l1 != null ? l1 : l2;
  return head.next;
};