Leetcode：刷完31道链表题的一点总结

前言

今天终于刷完了 Leetcode 上的链表专题，虽然只有 31 道题（总共是 35 道，但有 4 道题加了锁）而已，但也陆陆续续做了两三个星期，严重跟不上原先计划啊。先写一篇博客总结一下这阵子刷链表题的收获吧，有输入也要有输出。这里就不花篇幅介绍链表的一些基本概念了，不清楚的看官就自行百度一下吧，本文主要介绍一些常见的链表题和解题思路。

正文

缓存
不得不说使用数组 / map 来缓存链表中结点的信息是解决链表题的一大杀器，覆盖问题的范围包括但不限于：在链表中插入 / 删除结点、反向输出链表、链表排序、翻转链表、合并链表等，Leetcode 上 31 道链表绝大部分都可以使用这种方法解题。具体实现思路是先使用一个数组或者 map 来存储链表中的结点信息，比如结点的数据值等，之后根据题目要求对数组进行相关操作后，再重新把数组元素做为每一个结点连接成链表返回即可。虽然使用缓存来解链表题很 dirty，有违链表题的本意，而且空间复杂度也达到了 O(n)（即使我们常常用空间来换时间，不过还是能避免就避免吧），但这种方法的确很简单易懂，看完题目后几乎就可以马上动手不加思考地敲代码一次 AC 了，不像常规操作那样需要去考虑到很多边界情况和结点指向问题。

当然，并不是很提倡这种解法，这样就失去了做链表题的意义。如果只是一心想要解题 AC 的话那无妨。否则的话我建议可以使用数组缓存先 AC 一遍题，再使用常规方法解一次题，我个人就是这么刷链表题的。甚至使用常规方法的话，你还可以分别使用迭代和递归来解题，迭代写起来比较容易，而递归的难点在于把握递归边界和递归式，但只要理解清楚了的话，递归的代码写起来真的很少啊（后面会说到）。

先找道题 show the code 吧，不然只是单纯的说可能会半知半解。比如这道反转链表 II：反转从位置 m 到 n 的链表。如果使用数组缓存的话，这道题就很容易了。只需要两次遍历链表，第一次把从 m 到 n 的结点值缓存到一个数组中，第二次遍历的时候再替换掉链表上 m 到 n 的结点的值就可以了（是不是很简单很清晰啊，如果使用常规方法的话就复杂得多了）。实现代码如下：

var reverseBetween = function(head, m, n) {
  let arr = [];
  function fn(cur, operator) {
    let index = 1;
    let i = 0;
    while(cur) {
      if(index >= m && index <= n) {
        operator === "get" ?  arr.unshift(cur.val) : cur.val = arr[i++];
      }
      else if(index > n) {
        break;
      }
      index++;
      cur = cur.next;
    }
  }
  // 获取从 m 到 n 的结点数值
  fn(head, "get");
  // 重新赋值
  fn(head, "set");
  return head;
};

其他的题目例如链表排序、结点值交换等也是大致相同的代码，使用缓存解题就是这么简单。至于上面这题的常规解法，可以戳这里查看，我已经在代码中标注好解题思路了。

使用缓存来解题的时候，我们可以使用数组来存储信息，也可以使用 map，通常情况下两者是可以通用的。但因为数组和对象的下标只能是字符串，而 map 的键名可以是任意数据类型，所以 map 有时候能做一些数组无法做到的事。比如当我们要存储的不是结点值，而是整个结点的时候，这时候使用数组就无能为力了。举个例子，环形链表：判断一个链表中是否有环。先看一下环形链表长什么样。

还是使用缓存的方法，我们在遍历链表的过程中可以把整个结点当作键名放入到 map 中，并把它标记为 true 代表这个结点已经出现过。同时边判断 map 中以这个结点为键名的值是否为 true，是的话说明这个结点重复出现了两次，即这个链表有环。在这道题中我们是没办法用数组来缓存结点的，因为当我们把整个结点（一个对象）当作下标放入数组时，这个对象会先自动转化成字符串[object Object]再作为下标，所以这时候只要链表结点数量大于等于 2 的话，判断结果都会为 true。使用 map 解题的具体实现代码见下。

var hasCycle = function(head) {
  let map = new Map();
  while(head) {
    if(map.get(head) === true) {
      return true;
    }
    else {
      map.set(head, true);   
    }
    head = head.next;
  }
  return false;
}

}
Leetcode 上还有一道题充分体现了 map 缓存解题的强大，复制带随机指针的链表：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点，要求返回这个链表的深拷贝。具体的这里就不再多说了。此外，该题还有一种 O(1) 空间复杂度，O(n) 时间复杂度的解法（来自于《剑指offer》第187页）也很值得一学，推荐大家看看，详情可以看这里。