# 描述

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

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

题目链接:合并两个有序链表 (opens new window)

# 解法

# 递归

思路 分而治之, 自上而下的方式。 边界条件: 如果 l1 为 null, 则返回 l2, 说明, 反之。 递归条件:判断 l1 和 l2 头节点值得大小, 那个更小, 就把那个添加到上一个的前面。

let mergeTwoLists = function(l1, l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

# 迭代

当判断 l1 和 l2 都是 null 时,判断 l1 和 l2 的哪个头节点更小,然后将较小的节点添加到结果里,对应链表里应该移除当前节点然后后移一位。

思路: 1.新建一个空节点(headNode),然后维护一个 prev 指针,调整他的 next 指针。

  1. 判断 l1 和 l2 的值大小,如果 l1 < l2 就把 l1 当前的节点接到 prev 节点的后面,同时将 l1 的指针后移一位。否则,l2 也执行同样同样操作。
  2. 重复 2,直到 l1 或者 l2 为空后,将非空列表接在合并链表的后面,返回即可。
var mergeTwoLists = function(l1, l2) {
  let mergedHead = {
    val: "",
    next: null,
  };
  let crt = mergedHead; // 活动指针
  while (l1 && l2) {
    if (l1.val > l2.val) {
      crt.next = l2; // 拿出小值往前排
      l2 = l2.next; // 将 l2 重新赋值,相当于了删除了一个节点
    } else {
      crt.next = l1; //
      l1 = l1.next;
    }
    crt = crt.next; // 相等的情况
  }
  crt.next = l1 || l2;
  return mergedHead.next;
};

# 总结

总感觉 JS 实现的链表怪怪的,打印出来一堆对象套对象。

这一节涉及的知识挺多的,链表、递归。

上次更新: 3/4/2021, 3:37:55 PM