介绍

1、链表问题算法难度不高，但考察代码实现能力。
2、链表和数组都是一种线性结构。
①数组是一段连续的存储空间。
②链表空间不一定保证连续，为临时分配的。
3、链表分类
①根据指针的方向可以分为单向链表和双向链表
②根据有无循环可以分为普通链表和循环链表

链表问题代码实现的关键点：

1、链表调整函数的返回值往往是节点类型。
2、解决链表问题一定要花时间考虑哪些指针变了，一般可以用画图发辅助解决，在变化指针指向之前要保存环境，以免断线。
3、注意边界条件的处理：头节点、尾节点、空节点等特殊节点的处理

链表插入和删除的注意事项

1、要特殊处理空链表和长度为1的链表
2、插入之前要同时找到插入点之前和之后的位置
3、删除时要注意头尾节点及空节点，需要特殊考虑
4、单链表翻转
①为空和为1时要特殊处理
②大量链表问题可以使用额外数据结构来简化过程，但往往空间复杂度为O(1)即可解决

经典题

• 已知有序循环单链表，要求插入num并保持有序
  1、如果被插入的链表为空，这node自成循环链表
  2、如果不为空，用prior和current记录从head开始的相邻的两个节点，如果node在它们之间，则插入，否者prior和current指向下一个节点，如果循环一圈仍未找到插入位置，则将节点插入到head和rear之间（这时需要注意头结点的选择）
• 给定链表中节点node，但头节点未知，如何删除node。要求：时间复杂度为O(1)
  1、如果是双向链表，则可通过prior找到前一个节点，删除比较容易
  2、如果是单向链表，则一般通过替换法解决，即将需要删除节点的值替换为下一个节点的值，然后通过删除下一个节点来等效删除待删节点
  替换法的问题：1）如果需要删除的节点为尾节点，则该方法实效，2）工程上节点比较复杂时，复试节点的开销比较大，3）工程上有些情况禁止使用替换法，因为节点可能为外界提供服务，如果发生替换，则会给外界带来问题。
  替换法的一个不可行的替代方法：当要删除尾节点时，可能会考虑从内存的角度将该区域置空来达到与删除该节点等效的效果，但这是不可行的，因为内存中空是特殊的区域，如果想将某区域置空，则必须找到指向该区域的指针，而本题中这个指针是不可见的。