题型和题目

链表类型、操作集

链表vs.数组

链表考什么

链表为什么深受面试官青睐（何海涛）

链表的创建、插入、删除节点等操作都只需要20行左右代码就能实现，代码量比较适合作为面试题。由于链表是一种动态数据结构，其操作是针对指针进行的，因此应聘者需要有较好的编程功底才能编写出正确的操作链表的代码。另外，链表这种数据结构很灵活，面试官可以用链表设计出具有挑战性的面试题

哨兵节点（何海涛）

为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第2个节点开始才真正保存有意义的信息

1. 用哨兵节点简化链表插入操作
   链表的一个基本操作是在链表尾部添加一个节点。由于通常只有一个指向单向链表头节点的指针，因此需要遍历链表中的节点直至到达链表尾部，然后在尾部添加一个节点。将新创建的一个哨兵节点当作链表的头节点，链表无论如何非空，因此不需要使用if语句来单独处理输入头节点head为NULL的情形。哨兵节点简化了代码逻辑
2. 用哨兵节点简化链表删除操作
   为了删除一个节点，应该找到被删除节点的前一个节点，然后把该节点的next指针指向它下一个节点的下一个节点。这样下一个节点没有被其他节点引用，相当于被删除。如果没有哨兵，就要处理两个特殊情：输入的链表为空；被删除的节点是原始链表的头节点。如果在链表的最前面添加一个哨兵节点作为头节点，那么链表就非空，并且链表头节点无论如何都不会被删除。因此，也可以用哨兵节点来简化从链表中删除节点的代码逻辑

输入的链表为空，或者操作可能会产生新的头节点——这些都是应聘者在面试时特别容易忽视的测试用例。如果合理应用哨兵节点，就不再需要单独处理这些特殊的输入，从而杜绝由于忘记处理这些特殊输入而出现Bug的可能性

解题方法：双指针、递归

双指针思路又可以根据两个指针不同的移动方式细分成两种不同方法。第1种方法是前后双指针，即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后移动第2个指针。前后双指针的经典应用剑指 Offer 22. 链表中倒数第k个节点。先让第1个指针从链表头节点开始朝着指向下一个节点的指针先移动k-1步，然后让第2个指针指向链表的头节点，再让两个指针以相同速度一起移动，当第1个指针到达链表的尾节点时第2个指针正好指向倒数第k个节点

第2种方法是快慢双指针，通常快指针朝着指向下一个节点的指针一次移动2步，慢指针一次只移动1步。采用这种方法，在一个没有环的链表中，当快指针到达链表尾节点时慢指针正好指向链表中间节点。因此可以用来判断是否为环形链表141. 环形链表

Reference

古城算法.基础数据结构(五) —— 链表(上) 反转 + 合并 + 找环
古城算法.基础数据结构(五) —— 链表(下) 删除 + 复制 + 结构转换
何海涛.剑指Offer(专项突破版)：数据结构与算法名企面试题精讲[M]
图灵星球Turing Planet.Linked List链表题型解题套路和模板【LeetCode刷题套路教程4】