问题源于 leetcode 中的一道题:
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
就比方说下面这个图，就是返回那个红色的点
链表的数据结构：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
算法介绍
- 1 先定义两个指针，一个叫 fast，一个叫 slow，都指向链表中的第一个节点，
- 2 fast 一次向前走两步(fast = fast.next.next)，slow 一次走一步 (slow = slow.next)
- 3 如果这个链表中有环，那 fast 一定会在一圈后追上 slow 点，它们会在某处相遇
- 4 在相遇点，记录 slow 走过的路程为 x ，那么 fast 走过的路程就是 2x，即为 slow 再走 x 就与 fast 相同了
- 5 再把 slow 走过的路程 x 分成 y + z ，y 表示从起始点到红点的路程，z 表示从红点到相遇点的路程
- 6 那么把 4 和 5 结合起来看，让 slow 从相遇点再次开始走，它如果走 x ，它会回到自己的位置（由 4 得），而如果 slow 从红点开始走，走 z 会到达相遇点（由 5 得），那么它从相遇点开始走，走 y 就会回到红点，接下来确定 y 的位置就行了
- 7 让 slow2 和 slow 同时开始走(slow2 = slow2.next; slow = slow.next;)， 当它们同时走过 y，它们相遇的地方，就是红点
算法代码
public class Solution {
//这里给出的是链表的头节点
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
ListNode slow2 = head;
while (slow2 != slow){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}
