本文共 1454 字，大约阅读时间需要 4 分钟。
（1）链表问题算法难度不高，主要考察代码实现能力
（2）链表和数组都是一种线性结构
数组是一段连续分配的存储空间，
链表空间不一定保证连续，是临时分配的。（3）链表的分类
按链接方向分类：单链表、双链表
按有环无环分类：普通链表、循环链表循环链表是首尾相接的链表，它的最后一个元素的next指针指向它的第一个元素，
另外还有一种循环双链表，它的头节点还有一个指针指向它的最后一个元素。
（4）链表问题代码实现的关键
a.链表函数的返回值类型，要求往往是节点类型
b.处理链表过程中，先采用画图的方式理清逻辑，对解答很有帮助 c.链表问题对于边界条件讨论要求严格（5）链表插入和删除的注意事项
a.特殊处理链表为空，或者链表长度为1的情况
b.注意插入操作的调整过程头尾节点和空节点的注意。
（6）单链表的翻转操作
a.当链表为空，或者长度为1时，特殊处理。
b.对于一般情况的操作如下：首先用一个变量记录now结点的指向的下一个结点， 然后将now节点的next指针指向当前链表的head结点，将now节点设置为翻转部分的新的头结点， 最后根据之前的变量记录，重复进行这个操作。（7）关于额外空间的注意事项
大量链表问题可以使用额外数据结构来简化调整过程，
但链表问题最优解往往不是使用额外数据结构的方法。 很多问题都有空间复杂度为O(1)的解法。给定一个整数num，如何在节点值有序的环形链表中插入一个节点为num的节点，并且保证这个环形单链表依然有序。
首先生成节点值为num的节点node，
（1）如果链表为空
将node的next指针指向自己，返回node即可。
（2）如果链表不为空
令变量previous等于头结点，变量ncurrent等于头结点的下一个节点，两个指针同步移动下去，如果遇到p.value<=num，c.value>=num，
就把node插入其中，将node的prev指针指向当前的p，next指针指向当前的c即可。
（3）如果p和c转一圈都没有发现应该插入的位置，其实此时node的值应该是比链表中所有的值都大，或者都小，应该插入头节点的前面。但是注意，因为需要保证有序，所以两种情况下，链表的头部是不一样的。
给定一个链表中的节点node，但不给定整个链表的头节点，如何在链表中删除node？要求时间复杂度为O(1)，实现这个函数。
（1）如果是双链表比较简单，当前节点可以通过prev和next指针找到前后的节点，删除这个节点只需要将node的前后节点重新连接即可。
（2）单链表无法通过当前节点找到之前的节点，此时可以使用下面的思路。比如原始链表为1——>2——>3——>null，要删除节点2，但不知道头结点，
只要把节点2的值换成节点3的值，再链表中删掉节点3即可。 这种删除方式并不是删除了该删除的节点，而是进行了值的拷贝。 但是需要注意特殊情况： 如果要删除最后一个节点，因为节点3后面为空，只能将它删除，但找不到节点来替换，于是节点2的next指针不能指向null，删除失败。并且如果将节点3的值置为null，同样也是不可以的，此时节点2的指针仍然不是指向null。也就是说这道题目经常出现，但是题目本身是不完备的。
本文转自邴越博客园博客，原文链接：http://www.cnblogs.com/binyue/p/5213976.html，如需转载请自行联系原作者