算法题套路总结（一）——链表

最近也做了很多题目，但是回过头一看发现好多题目虽然当时是我独立思考出来的，但是我又忘了该怎么做了，又得花好长时间是思考。不过想来想去发现其实大部分题目还是有套路的，所以我觉得是时候去总结一下这些套路。这是个系列文章，将会总结一些常见题型的套路。第一篇先说说链表。我遇见的所有算法题目所涉及到的链表，都是单链表，因此这里也只说单链表。

单链表其实就是一个data加上一个next指针。由于一个节点只通过next指针保存了它的下一个节点，失去了它的前驱节点信息，因此几乎所有单链表题目都是在前驱节点做文章。同时，单链表数据结构通常长度未知，很多题目也会在长度上做文章。基本上思考链表题目就这么两个思路下手。

围绕这两个问题，链表大致有以下几种经典题型：

• 双指针
• 模拟高精度加减法
• 翻转链表（全部or部分）

双指针

针对于双指针，实际上更细化也分两种：

• 快慢指针
• 前后指针

比如说:

• 19. 删除链表的倒数第N个节点，链表涉及到长度，马上应该联想到双指针。由于长度未知，倒数第N个怎么找？两个指针，第一个先走N步，第二个原地不动。然后一起遍历，当前面指针到最后时，后面的指针就指向倒数第N

• 61. 旋转链表，旋转k相当于把尾节点连到头结点，然后在倒数第k个节点处断开。但是这里需要遍历一次链表取得总长度n，因为k很可能非常大，需要对n取模。也是一个经典的前后指针的运用

• 环形链表，判断链表是否有环。链表有环说明next永远不为None，此时采用快慢指针，一个指针快（一次走2步）一个指针慢（一次走1步），如果有环，快指针某个时刻就会追上满指针（跑步超圈）。如果快指针走到None节点，说明无环。

针对链表的环，其实也有两个经典题目，一个是求环的起点142. 环形链表 II
，一个是求环的长度。
求环的长度其实可以转化成小学数学的追及问题。当快慢指针第一次相遇时，此时节点肯定在环上某个位置。我们以此为起点继续走，同时记录步数t。当快慢指针再次相遇时，相当于速度为2的经过t秒比速度为1的多跑了一圈，2*t-1*t=t，因此环的长度就是t
而求环的起点则稍微需要画个图来理解。（暂时缺图，后面补，证明过程在图上）总之结论就是，当快慢指针第一次相遇后，慢指针到环的起点的距离和链表头指针到环起点距离相等。也就是说，此时利用一个新的指针，从头开始走，当和慢指针相遇时，该节点就是环的起点。

环形链表的一个变种就是求两个链表的交点，比如160. 相交链表。这道题表面上看起来有两个链表，不过如果做一个辅助线，比如把B链表首尾相连，也就是让链表的末节点指向B链表的表头，那么这道题就变成了求单链表的环的起点。当然这种思路就需要做题时积累了，临场想的话还是稍微有点费劲。

翻转链表

翻转链表就是很直接的题目，主要是考实现而不是考算法。翻转链表的题目就比较种类繁多了，但各种翻转都万变不离其宗。只要掌握了翻转整个链表的方法，剩下大部分的都是花式处理边界case。

fn reverse_list(mut head: Option<Box<ListNode>>) ->   
  Option<Box<ListNode>> {
  let mut new_head = None;
  while let Some(node) = head.take() {
    let new_node = ListNode{
        val: node.val,
        next: new_head.take(),
    };
    new_head = new_node;
    head = node.next;
  }
  new_head
}

以上是通过新建链表来进行翻转，实际上还可以原地翻转，Rust不太方便实现，Go的伪代码如下：

func reverseLinkedList(head *ListNode) *ListNode {
  if head == nil {
    return nil
  }
  var newHead *ListNode
  cur := head
  for cur != nil {
    next := cur.Next
    cur.Next = newHead
    newHead = cur
    cur = next
  }
  return newHead
}

这种原地翻转实际上只是改变了节点指针的指向，更简单了。

由于直接翻转链表很简单，因此大部分题目都是花式翻转，比如：

• 25. K 个一组翻转链表和24. 两两交换链表中的节点（相当于K=2）,当我们在翻转链表中的连续k个节点时，实际上和翻转整个链表没有区别。但是需要注意的是，翻转完的链表需要接到之前的链表后面，即pre.Next = newHead，同时，因为要继续翻转接下来的k个，因此还要记录翻转后链表的尾节点。当发现最后一次不足k个时，还要把已经翻转的链表再翻转回去。

• 234. 回文链表，判断一个链表是否是回文的，利用快慢指针找到中点，然后把后半部分翻转。如果是回文的，翻转之后后半部分和前半部分应该是一样的

• 143. 重排链表，要把L0->L1->L2->L3->L4变成L0->L4->L1->L3->L2，其实相当于把链表前一半不动L0->L1->L2，后一半翻转L4->L3，然后把翻转后的节点插入到前一半链表的缝隙中L0-> (L4) -> L1-> (L3) -> L2。关键词一半、翻转。因此，利用快慢指针找到前一半，然后把后一半翻转，最后再插空。

翻转链表变种题目，大多数可能需要开辟额外空间或者建立新的虚拟链表，最终再拼接回去。比如：

• 86. 分隔链表，给链表重新排序，小于x的元素要在大于等于x的元素的前面，剩下的元素相对顺序不变。这道题就可以建立两个虚拟链表，小于x的放到before链表中，大于等于的放到after链表，最终再把after放到before后面。
• 328. 奇偶链表，同样建立两个虚拟链表，一个保存奇数个节点一个保存偶数个，最后合并回去
• 725. 分隔链表，先求出链表总长度n，然后计算每个部分要放几个元素，前n%k个部分要多一个元素，直接遍历即可。

高精度运算

这类题不多，但是其实解法很简单。因为加减法涉及到进位，所以先翻转链表，然后进行加法操作即可。

总结

经过上面的总结，其实链表基本就这么些题型，只要掌握了这些题型和核心解题思路，拿起双指针和翻转两大武器，基本上就不怕链表的题目了。