剑指offer专项突破版

链表

1. 一个操作可能产生新的头节点，则可以尝试在链表的最前面添加一个哨兵节点来简化代码逻辑，降低代码出现问题的可能性。
2. 双指针是解决与链表相关的面试题的一种常用技术。前后双指针思路让一个指针提前走若干步，然后将第2个指针指向头节点，两个指针以相同的速度一起走。快慢双指针让快的指针每次走两步而慢的指针每次只走一步。
3. 大部分与链表相关的面试题都是考查单向链表的操作。单向链表的特点是只能从前往后遍历而不能从后往前遍历。如果不得不从后往前遍历链表，则可以把链表反转之后再遍历。
4. 如果链表中的节点除了有指向下一个节点的指针，还有指向前一个节点的指针，那么该链表就是双向链表。由于双向链表的操作牵涉到的指针比较多，因此应聘者在解决面试题的时候要格外小心，确保每个指针都指向了正确的位置。
5. 循环链表是一种特殊形态的链表，它的所有节点都在一个环中。在解决与循环链表相关的面试题时需要特别注意避免死循环，遍历链表时等所有节点都遍历完就要停止，不能一直在里面绕圈子出不来。