单链表成环寻找
众所周知， 单链表是一个非常常用和常见的数据结构，一个节点包含一个值以及下一个节点。用代码表示
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
next = null;
}
}
或者， 在C语言里面可以这么进行表示（有很多实现方法， 例如数组，但是这里就用比较简单和直接的一个方法）
typedef struct T{
int x;
struct T* next;
}Node;
显而易见，有时候链表会有成环的情况。那么我们有什么办法来寻找这种情况呢？
有一种最暴力的方法， 就是开一个Map， 来记录我们走过的地方，当重合了，也就自然发现了成环的情况。但是这样的一个坏处是， 我们需要付出O(n)的空间来完成这个任务。那么我们有别的办法来完成吗？
快慢指针
此处引用Leetcode 的一个题目： LeetCode 142 LinkedList Cycle II
其实说白了也很简单，就是小学学过的追及问题。 不多跟你们BB, 上代码(talk is cheap, show me the code)：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null; // 如果都是空的， 没啥好bb的
ListNode fast = head; // 快指针
ListNode slow = head;// 慢的
boolean isLoop = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
isLoop = true;
break;
}
}
if (isLoop) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
return null;
}
}
C 语言的， 也是类似。
