您现在的位置是：首页 >技术杂谈 >学习数据结构（7）单链表OJ下+链表分类网站首页技术杂谈

1.链表的回文结构

解法一：（投机取巧的办法）由于题目中保证链表长度小于等于900，所以可以创建一个长度为900的数组，通过遍历将链表中的数据依次储存到数组中，再在左下标小于等于右下标的情况下，从数组两端同时遍历，若数组元素不相等，返回false，否则返回true

解法二：（参考解法）先找到链表的中间节点，以中间节点为首节点，将首节点以后的链表反转，得到新的首节点，分别从原链表的首节点和新的首节点开始，在新的首节点不为NULL的条件下同时遍历，如果节点储存的数据不相等，返回false，否则返回true

2.相交链表

解法一:（参考解法）由于两个链表的长度不确定，所以不能直接同时遍历两个链表，可以先分别遍历两个链表，求出两个链表相差的长度，让长链表先走，对齐长度，再同时遍历两个链表，如果有链表储存的数据不同，返回flase，否则返回true

（另外还有一种思路，将两个链表反转，从反转后的首节点开始同时遍历，若某个节点的next不同，则返回这个节点，但题目中要求，所以本题不考虑）

3.环形链表Ⅰ

解法一：（快慢指针）

首先必须证明一个结论：在环形链表中，快慢指针同时从链表起始位置开始运动，其中慢指针一次走一步，快指针一次走两步， 快慢指针一定会相遇

假设slow刚到入环节点时，fast在如图所示的位置，此时fast与slow之间的距离为N，由于fast每次走两步，slow每次走一步，所以每运动一次fast和slow之间的距离就会减少一步，故只要运动的次数足够多，fast和slow之间的距离一定会减为0，即fast和slow相遇

所以让fast和slow在fast和fast->next同时存在的情况下，同时从首节点开始运动，如果出现fast==slow,则返回true，否则返回false

快指针如果一次走3步、4步、5步……n步，快慢指针都一定会相遇吗？

下面证明快指针走三步的情况：

C为环形部分的周长，假设slow刚到入环节点时，fast在如图所示的位置，此时fast与slow之间的距离为N，由于fast每次走三步，slow每次走一步，所以每运动一次fast和slow之间的距离就会减少两步，若N为偶数，则N不断减2最终可以为0，即fast和slow相遇，若N为奇数，N会减为-1,此时slow和fast错过，fast和slow之间的距离变为C-1，若C-1为偶数（即C为奇数），则fast和slow可以相遇，若C-1为奇数（即C为偶数），则fast和slow还是不能相遇，最终也不会相遇

由于fast每次走三步。slow每次走一步，所以fast的总路程一定是slow的三倍，如上图所示，此时fast的路程为L+xC+C-N，slow的路程为L，代入关系式，得2L=(x+1)C-N

对上式进行分析，2L是偶数，偶数=偶数-偶数或奇数-奇数，当(x+1)C为奇数，N为奇数时，由于奇数只可能等于奇数×奇数，所以(x+1)一定为奇数，C也一定为奇数，故N为奇数，C为偶数的情况不存在，也就是说，只存在两种情况：N为偶数，C为奇数；N为奇数，C为奇数，故fast和slow一定会相遇

其他情况的证明方法同上

在环形链表中，slow一次走一步，无论fast一次走多少步，fast和slow最终一定会相遇

fast走三步时的代码：

为了方便写代码，通常使用快指针走两步，慢指针走一步即可

4.环形链表Ⅱ

解法一：(参考解法)解这道题之前首先得证明一个结论：快慢指针相遇点（即判环点）到入环口的距离与链表起始点到入环口的距离相等

相遇时快指针走的总路程为L+C-N+xC，慢指针走的总路程为L+C-N，由于快指针所走路程为慢指针的两倍，代入关系式，得L=xC-(C-N)=(x-1)C+N（x=1，2，3....，x的值取决于环的大小，环越小x越大），取x=1,得L=N，即链表起点到入环点的距离与相遇点到入环点的距离相等

也就是说，如果一个指针从链表起点开始运动，同时另一个指针从相遇点开始运动，都一次走一步，那么这两个指针最终会在入环点相遇

参考代码：

5.链表的分类

链表的结构虽然有八种，但最常用的还是不带头单向不循环链表和带头双向循环链表，头节点指的是不储存数据的节点（哨兵位），不带头单向不循环链表结构简单，一般不单独用来储存数据，带头双向循环链表结构最复杂，一般用在单独储存数据