leetcode刷题

leetcode 142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

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

不允许修改链表。

示例1

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

示例2

解法1

hashmap,

缺点，占内存

解法2 双指针找规律

先设置一个快慢指针（快指针1次跑2个节点慢指针一次1个节点）从头开始跑，第一次相遇时，必然因为环的原因相遇，(不然怎么相遇？)
- 之所以相遇是因为快指针在环内把把慢指针套了圈，也即
  $f=s+2nb$
又因为快指针移动距离是慢指针两倍
```
联立得： 
```

设计第二次相遇机会，将原来得快指针重新指向头节点，慢指针位置不变（注意现在$f$ 比 $s$“快了” $nb$ 步）
改变移动规则，快指针和慢指针每次都只移动一次

那么，节点必定在环形入口相遇，且移动距离就是非环部分的长度 $a$！因为这时 $f=a$ ; $s=a+nb$

返回这个节点即可

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    // 构造第一次相遇
    while(true){
        if( fast==null || fast.next == null) return null;
        
        fast= fast.next.next;
        slow = slow.next;
        if(fast==slow){
            break;
        }
    }
    //构建第二次相遇
    fast = head;
    while(fast!=slow){
        fast=fast.next;
        slow=slow.next;
    }
    return fast;
}