前端刷题路-Day56：合并两个有序链表（题号21）-一一网

这是我参与更文挑战的第20天，活动详情查看：更文挑战

合并两个有序链表（题号21）

题目

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
复制代码

示例 2：

输入：l1 = [], l2 = []
输出：[]
复制代码

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
复制代码

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

链接

leetcode-cn.com/problems/me…

解释

这题啊，这题是经典链表题。

这题的主要逻辑有两个：

有一条链表没了怎么办
两条链表的节点插入顺序是什么

第一个问题很好解决，如果有一条链表走到头了，那么结果必然是当前的链表接上另外一条链表，不管另外一条链表是不是null，连上返回就完事了。

第二个问题也很简单，判断两个链接的头节点，取较小的那个头节点赋值给最后要返回的链表，然后当前链表向后走一个节点。如果头结点一样大，那就随便取一个，这题不需要考虑大于等于的关系，因为一样大的情况不需要考虑顺序。

弄清楚这两个点就会发现这题其实非常简单，考的其实是具体的实现方式。

笔者这里就比较弱了，虽然也是实现了，但是代码比较丑陋，而且没有剪枝。

自己的答案（迭代）

先看代码?：

var mergeTwoLists = function(l1, l2) {
  var head = new ListNode(0)
      node = head
  while (l1 || l2) {
    if ((!l1 && l2) || l2 && l1.val >= l2.val) {
      node.next = l2
      node = node.next
      l2 = l2.next
    } else {
      node.next = l1
      node = node.next 
      l1 = l1.next
    }
  }
  return head.next
};
复制代码

整体逻辑和思路是没问题的，重点是在一条链表走到头的时候没有直接赋值剩余节点，而是傻傻的继续赋值，这里完全没有必要这么做，纯属浪费。

而且if的条件写的太复杂了，正常人第一眼看过应该得反应一会，其实就总结了所有需要采l2节点的情况，剩下的自然就是用l1节点了。

不推荐。

更好的方法（迭代）

让我们看看官方的迭代解法了，神清气爽?：

var mergeTwoLists = function(l1, l2) {
  var head = new ListNode(-1)
      node = head
  while (l1 && l2) {
    if (l1.val < l2.val) {
      node.next = l1
      l1 = l1.next
    } else {
      node.next = l2
      l2 = l2.next
    }
    node = node.next
  }
  node.next = l1 ? l1 : l2
  return head.next
};
复制代码

这里其实笔者进行了一些简化，去掉了!== null的判断，直接利用JavaScript中的隐式转换来进行判断l1和l2是否为null。

其次，官方的迭代只有在l1和l2同时存在时才会进行，取二者中较小的进行赋值操作。

在迭代到两个链表中一个的尽头时终止迭代，然后进行最后的赋值。

更好的方法（递归）

这题的递归解法就比较巧妙了，不像其他题目一样还需要在函数本体中新增参数，只靠l1和l2两个参数就能完成递归?：

var mergeTwoLists = function(l1, l2) {
  if (!l1 && !l2) return null
  if (!l1) {
    return l2
  } else if (!l2) {
    return l1
  } else if (l1.val >= l2.val) {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  } else {
    l1.next = mergeTwoLists(l2, l1.next)
    return l1
  }
};
复制代码

首先是两个链表都走到头了，直接返回null，之后判断如果两个链表只剩一条的情况下，直接返回存在的那条节点。

接下来就是重头戏了，这里直接改变了较小值节点的next属性，赋值为下一步递归的结果。下一步递归的参数赋值变化的只有较小的节点链表，这个链表走了一个节点，另一条节点不变。

这就完事了，简直不要太简单，看完这个答案后简直豁然开朗，看来是还没有理解递归的真谛啊。

原来笔者理解递归还存在初级阶段?：

腐烂的橘子