所谓拳不离手曲不离口，算法和基础不能丢。
话说三藏师徒四人辞别女儿国，再上西行路，今天来到。。。啊呸，扯远了。。
今天来看这个，https://oj.leetcode.com/proble…，题目是这么说的
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
这题原本是简单，他页面上提供了一个在线的编辑器，带语法高亮和自动补全，我三分钟直接在线写完，一次性提交就编译通过同时 Accepted，想想上次刷 OJ 还是很久之前了，如今依然没有手生，还是很开心的，土豪解法如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
#include <set>
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* curr = head;
while (curr) {
if (viewed.find(curr) != viewed.end()) {
return true;
}
viewed.insert(curr);
curr = curr->next;
}
return false;
}
std::set<ListNode*> viewed;
};
类和函数是他给好的，我们要做的就是在类里面填空而已。
可以看到，这个解法不论是在时间还是空间上，都是土豪，何止土豪，那是相当土豪。不过，实际项目中，其实这么写是可以的，稳定，不出错，可维护性高。
不过，原题里还有这么一句，Can you solve it without using extra space?，这个很明显就是见功夫的地方了，要抠时间和空间，时间上是没啥可压缩了，至少也要遍历一次，空间上嘛，他要求没有额外空间，怎么搞呢，想了想，想起来之前看书的时候看到这个题，当时说的是，用两个指针，一个每次走一步，一个每次走两步，如果这两个指针遇上了，那么就说明有环，具体写起来，可以这么写：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (1) {
if (slow) {
slow = slow->next;
}
if (fast) {
fast = fast->next;
if (fast) {
fast = fast->next;
}
}
if (fast == NULL && slow == NULL) {
return false;
}
if (slow == fast) {
return true;
}
}
}
};
又是一次 Accepted，我都怀疑是不是用例太弱了。。
需要注意的是，如果把最后的两个 if 判断对调位置，变成这样
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (1) {
if (slow) {
slow = slow->next;
}
if (fast) {
fast = fast->next;
if (fast) {
fast = fast->next;
}
}
if (slow == fast) {
return true;
}
if (fast == NULL && slow == NULL) {
return false;
}
}
}
};
那就会导致 WA，具体为什么可以想想，不难想出来。
不过，这个题目还有一个变式，要求找出环的入口节点，题目在这里，https://oj.leetcode.com/proble…，这个题的解法很是有技巧，分析思路可以看到这里，http://blog.reetsee.com/archiv…
我们设链表的无环的部分长度为L1，即有L1个节点，注意，这个L1是包括环的入口节点的。然后让环的长度是L2，这个L2也是包括环的入口节点。这个时候，p1和p2的交点如图所示，交点距离环的入口节点为a（从入口节点沿着行走方向走到交点），即在环的入口节点后面的第a个节点，就是交点，我用红色标记出a。
然后我们来考察一下L1，L2，a，以及n（n是走过的步数，不是走过的节点数，p1一步一个节点，p2一步两个节点）的关系。
忘记说一点了，我们可以明确的是，p1在进入环后，走了不到一圈就在交点处和p2重合，為什麼肯定没有走完一圈？因为p1在进入环的时候，p2和p1之间的距离（沿着行走方向）至多为 L2-1，不可能超过L2-1，因为环的大小也才只有L2 。p2追赶p1，最多只需要走L2-1步，因为每走一步，p1和p2的相对距离减小1，那么p1最多只走了L2-1步，就是最多只经过了L2-1个节点，不可能走完一圈。
现在可以列公式了：
L1+a=n #1 //n是p1走过的节点数
L1+k*L2+a=2*n #2 //2*n这个是p2走过的节点数，其中的k表示p2可能在环里面走了k圈，k>=1
由#2式减去#1式，有：k*L2 = n #3
同时由#1和#3得到：L1+a = k*L2 #4
接着由#4就得到了如下式：L1 = k*L2 – a = (k-1)*L2 + (L-a)
得到这条式子就拨得云开见月明啊有木有，因为(L-a)表示的是交点与环入口的距离（从交点沿着行走方向到环入口），然后(k-1)是>=0的，因为p2在环中至少绕了一圈，这样我们就发现：L1的长度 = 环长度的整数倍 + 交点与环入口的距离也就是说，p1再走L1步就可以达到环的入口。问题是L1不是已知的，没关系，在表头设置一个p3指针，p3每步前进一个节点。让p1和p3同时走，每次走1步，等p3和p1重合了，就是到了环口的位置了。Problem solved~
很自然的，写出下面的代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast(head), *slow(head), *p1(head);
while (1) {
if (slow) {
slow = slow->next;
}
if (fast) {
fast = fast->next;
if (fast) {
fast = fast->next;
}
}
if (fast == NULL && slow == NULL) {
return NULL;
}
if (slow == fast) {
while (1) {
slow = slow->next;
p1 = p1->next;
if (p1 == slow) {
return p1;
}
}
}
}
}
};
但是这样是 WA 的，OJ 很仁慈的把错误说出来了
Input: {1,2}, tail connects to node index 0
Output: tail connects to node index 1
Expected: tail connects to node index 0
也就是说，考虑这种情况：整个链表只有两个节点，并且这两个节点构成一个环，那么上述代码就出错了，打个补丁：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast(head), *slow(head), *p1(head);
while (1) {
if (slow) {
slow = slow->next;
}
if (fast) {
fast = fast->next;
if (fast) {
fast = fast->next;
}
}
if (fast == NULL && slow == NULL) {
return NULL;
}
if (slow == fast) {
if (slow == head) {
return head;
}
while (1) {
slow = slow->next;
p1 = p1->next;
if (p1 == slow) {
return p1;
}
}
}
}
}
};
得以 Accepted，而其实，上述的代码，是可以进一步改的，注意到我们外面的那个循环，为了保守起见，是等慢指针遍历到尾，才退出的，其实根本没必要，只要快指针遇到 NULL 了，就可以撤了，如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast(head), *slow(head);
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *p(head);
while (p != slow) {
slow = slow->next;
p = p->next;
}
return p;
}
}
return NULL;
}
};
——————————–
2014-11-21 09:43:45 update
另外的一个思路是，每次前进一个节点，就把这个节点的 next 指针指向 head，这样，如果发现在某个节点被处理之前，就已经指向 head，那么就可以知道有环了，而且这个方法还可以天然的找出环的入口，不需要额外空间，缺点是破坏链表，一次处理之后，链表就被破坏的面目全非了。
这个思路尚未经过实际代码验证。
真有闲情逸致….