【LeetCode】环路检测（链表）

链表回环问题：

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：tail connects to node index 1

解释：链表中有一个环，其尾部连接到第二个节点。

哈希表解法：

从前到后依次的去遍历并加入到哈希表中，第一个出现重复的结点就是这个环的开头结点！

public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<ListNode>();
		
		while(head!=null) {
			if(set.contains(head))
				return head;
			set.add(head);
			head = head.next;
		}
		
		return null;
    }
           

快慢指针解法：

思路与算法

我们使用两个指针，fast 与slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则fast 指针最终将再次与slow 指针在环中相遇。

如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

根据题意，任意时刻，fast 指针走过的距离都为slow 指针的 2 倍。因此：

a+(n+1)b+nc= 2(a+b) ==> a=c+(n-1)(b+c) ==> a = c

通过上面的等式可以得出结论：当slow与fast相遇时，a这个距离是等于c这个距离的，所以这时定义一个pre指针指向链表的表头，pre与slow都一步一步的走，在pre与slow相遇时，它们指向的结点就是环的开头结点了！

public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
		ListNode fast = head;
		
		while(true) {
			if(fast==null||fast.next==null)
				return null;
			slow = slow.next;
			fast = fast.next.next;
			if(slow==fast)
				break;
		}
		
		ListNode pre = head;
		
		while(pre!=slow) {
			pre = pre.next;
			slow = slow.next;
		}
		
		return pre;
    }
           

第二种快慢指针的解法，如果光看的话太抽象了，找不到什么关系，通过数学逻辑去分析把这些抽象的东西用变量代替然后写出等式，将这些抽象的关系用数学逻辑关联到了一起，答案一下就清晰了。