算法第36题--找到链表中的环

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

/**
 * 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) {
        /**
        思路1：使用一个set集合，遍历链表元素，如果有环存在，那么set集合中一定包含这个元素，直接返回即可
        思路2：使用快慢指针
        （1）快指针一次走两步，慢指针一次走一步。
        （2）假如有环，那么快指针一定会在某个时刻追上慢指针
        （3）假设非环部分的长度为a，环的长度为b，快指针走了f步，慢指针走了s步
        （4）那么首先有f=2s（两倍的步长），当重合的时候，快指针一定比慢指针走了一倍的路程
        （5）其次因为在环中相遇，所以重合的时候，快指针在环内一定比慢指针多跑了n圈
        即假设非环部分长度为a，环长度为b,一定有 f = nb + s 
        （6）两式相减 nb = s
        （7）
         */
         // 使用set集合来做
         /**
         HashSet set = new HashSet();
         ListNode node = head;
         while(null != node){
             if(set.contains(node)){
                 return node;
             }
             set.add(node);
             node = node.next;
         }
         return null;
          */
          // 使用快慢指针来做
          ListNode slow = head;
          ListNode fast = head;
          // 先确认是否有环
          // 找到环的位置后，slow位置不变，fast指针从head头位置一步一步走，当和slow相遇的时候，就是环入口
          while(true){
              if (fast == null || fast.next == null) return null;
              fast = fast.next.next;
              slow = slow.next;
              if(slow == fast) break;
          }
          fast = head;
          // 找到入口
          while(fast!=slow){
              fast = fast.next;
              slow = slow.next;
          }
          return fast;
    }
}