1.链表有关的知识

（1）链表问题算法难度不高，主要考察代码实现能力

（2）链表和数组都是一种线性结构

数组是一段连续分配的存储空间，
链表空间不一定保证连续，是临时分配的。

（3）链表的分类

按链接方向分类：单链表、双链表
按有环无环分类：普通链表、循环链表

循环链表是首尾相接的链表，它的最后一个元素的next指针指向它的第一个元素，

另外还有一种循环双链表，它的头节点还有一个指针指向它的最后一个元素。

（4）链表问题代码实现的关键

a.链表函数的返回值类型，要求往往是节点类型
b.处理链表过程中，先采用画图的方式理清逻辑，对解答很有帮助
c.链表问题对于边界条件讨论要求严格

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

a.特殊处理链表为空，或者链表长度为1的情况
b.注意插入操作的调整过程

头尾节点和空节点的注意。

（6）单链表的翻转操作

a.当链表为空，或者长度为1时，特殊处理。
b.对于一般情况的操作如下：
首先用一个变量记录now结点的指向的下一个结点，
然后将now节点的next指针指向当前链表的head结点，
将now节点设置为翻转部分的新的头结点，
最后根据之前的变量记录，重复进行这个操作。

（7）关于额外空间的注意事项

大量链表问题可以使用额外数据结构来简化调整过程，
但链表问题最优解往往不是使用额外数据结构的方法。
很多问题都有空间复杂度为O(1)的解法。

2.环形链表插值问题

给定一个整数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的值应该是比链表中所有的值都大，或者都小，应该插入头节点的前面。但是注意，因为需要保证有序，所以两种情况下，链表的头部是不一样的。

3.访问单个节点的链表删除题目

给定一个链表中的节点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，如需转载请自行联系原作者