链表必知必会

链表的特点

相比于数组，链表的优点是插入删除只有 O(1)的时间复杂度。如果数据的长度无法估量，或者需要频繁的插入删除，可能就是需要链表了。

快慢指针

对于链表，一定要知道的是快慢指针的应用。快慢指针一个应用是用来判断有没有环，和寻找环的入口。

判断有没有环

141. 环形链表

var hasCycle = function (head) {
  let slow = head, fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next
    fast = fast.next
    if (slow === fast) return true
  }
  return false
};
复制代码

• 时间复杂度 O(n)
• 空间复杂度 O(1)

慢指针每次走一步，快指针每次走两步，如果没有环，不会相遇。

进入环后，假设快慢指针相差 n 步，因为快慢指针是同一方向，快指针每次追上慢指针 1 步，也就是每次行进，快慢指针的距离都会缩短 1 步，这样经过 n 次，快指针一定会追上慢指针，快慢指针一定在环中相遇。

寻找环的入口

142. 环形链表 II

• a 为从根结点到环形入口的距离
• b 为慢指针从入口到相遇点的距离
• c 为慢指针从相遇点到入口的距离

简单来说，记住这个结论 a = c

对于算法来说，知道这个结论就足够了。但为了能记的长久，还是得亲自推导一下。

首先要知道的是，慢指针在环内一定是在一圈内与快指针相遇。如果快指针落后慢指针一圈，慢指针走一圈，快指针才能追上。 在环内，快指针落后慢指针的距离小于一圈，所以慢指针不需要走满一圈就一定会被快指针追上.

快指针走的路程是慢指针的两倍，设相遇时快指针已经在环内走了 n 圈。

a + b + (b + c) * n = 2 * (a + b)
复制代码

两边消掉一个 a+b

(b + c) * n = a + b
复制代码

当 n 为 1 的时候 a = c

当 n 不为 1 的时候呢， 我们把 b 移过去

a = (b + c) * n - b
复制代码

无论 n 是多少都可以从 a 里减掉 最后只剩 1 圈，对应于算法就是 代表 a 的指针 p 不断向前走，环内的 slow指针不断转圈，最后一定会到达到这样的状态

a = (b + c) * 1 - b
复制代码

也就是 a = c 一定能在环口相遇。

一圈时 a 实际长度和 n 圈时 a 的实际长度不同。a 代表的是环外走多少距离能在环口和慢指针相遇。

var detectCycle = function (head) {
  if (!head || !head.next) return null
  let slow = head, fast = head
  while (fast && fast.next) {
    fast = fast.next
    fast = fast.next
    slow = slow.next
    if (slow === fast) break
  }
  if (slow !== fast) return null
  let p = head
  while (p !== slow) {
    p = p.next
    slow = slow.next
  }
  return p
};
复制代码

• 时间复杂度 O(n)
• 空间复杂度 O(1)

常用算法

链表的算法一般都能想出来，但是可能写不出来。比如反转链表，一想谁都懂，但是如果平时没练过，在面试的时候大概率是写不对的，即使勉强写对了，也会写的很难看。所以练好基本功特别重要。平时能不假思索就写，在用到的时候才能快速准确的写出来。

对于常用算法是需要背下来的。不要觉得背算法是丢人的事，会让人觉得笨。试想一下，我们能快速解决问题，不就是因为已知很多结论吗？象公式公理，不用每次都要推导一次，拿过来用就可以。 对于常用算法也是一样，只有背下来，以这些为基础，才能快速解决其它的复杂问题。

删除一个节点

p.next = p.next.next
复制代码

这句代码很重要，这是解决删除类问题的基础，遇到删除类的问题，记住每次只删除一个节点，不要想着一次删除很多节点。每次只删除一个节点是通用作法。

1. 83. 删除排序链表中的重复元素
2. 82. 删除排序链表中的重复元素 II
3. 19. 删除链表的倒数第 N 个结点

反转链表

206. 反转链表

这道很有代表性，体现了链表算法的一个特点，就看基本功是不是扎实。对于反转链表需要用三个指针。自己多写几次。背下来。

var reverseList = function (head) {
  if (!head || !head.next) return head
  let cur = head, prev = null, next = null
  while (cur) {
    next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
};
复制代码

92. 反转链表 II

增删查

707. 设计链表

这道题目包含了增加，删除，查找的基本操作。需要熟练掌握。相对于实现，更重要的是体会设计的思想，链表的头指针默认会有，但是尾指针和长度 size 可能没有。这就需要我们根据实际需求设计出合适的链表算法。

其它常见算法

1. 60. 相交链表
2. 24. 两两交换链表中的节点
3. 21. 合并两个有序链表
4. 725. 分隔链表

链表算法技巧

临时节点

一般写做 dummy。 你也可以叫其它名字，不过用 dummy 可读性会好些。用 dummy可会简化写法。

const dummy = new NodeList(null,head)
复制代码

当你发现需要特殊处理头节点的时候，就可以考虑加一个 dummy 试试。

先解决空链表

if(!head ||!head.next) return head
复制代码

写正文前，不管有用没用，先把这句写上，会少很多麻烦。当然也要注意返回值是不是要返回头节点

链表的算法实现

链表作为简单数据结构，一般来说，都能想出算法。实在不行，可以把链表转成数组，也可以直接交换值，而不是实际交换节点（面试的时候可千万别这么说）。任何算法都是用它的可取之处的，就看是不是用对了地方。

一般来说，会有迭代法和递归法。递归法需要额外的 O(n)空间，所以实际并不推荐使用。但作为一种算法思想还是需要了解的。有的时候递归法会更加简洁。

在算法实现的时候，还是优先选好理解的算法，除非有明显的优势。