142. 环形链表 II

1、题目描述

 2、基础前提，链表实现结构体

基础前提，链表实现结构体：

class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
       this.val = val;
    }
}

3、解题思路

根据题目，如果存在环，需要求返还环的交叉点。

相关比较容易想的思路是，我们把所有节点及相关的下标存入哈希表中，如果哈希表已经存在该节点，就是环的交叉点，这个时候如果哈希表已经存在该节点了，直接返回节点即可。

3-1、哈希表方法

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

复杂度分析

时间复杂度：O(N)，其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。

空间复杂度：O(N)，其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。

3-2、快慢指针

使用两个指针，fast 与 slow， slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

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)

从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

对应的代码实现：

public class Solution {
    public ListNode detectCycle(ListNode head) {
       if(head == null || head.next == null) return null;
       //设置快慢指针
       ListNode fast = head, slow = head;
       while(fast != null ){
          slow = slow.next;
          if(fast.next != null){
             fast = fast.next.next;
          }else{
             return null;
          }
             
          if(slow == fast){
             //创建新指针，指向链表头
             ListNode ptr = head;
             while(ptr != slow){
                ptr= ptr.next;
                slow = slow.next;
             }
             return ptr;
          }
       }
       return null;
    }
}

复杂度分析

时间复杂度：O(N)，其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)。

空间复杂度：O(1)。我们只使用了 slow,fast,ptr 三个指针。

【快慢指针，难点在于找到对应的恒等式】