【LeetCode】【算法】142. 环形链表II

142环形链表II

题目描述

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

做题思路

这道题实际就做两件事：
第一件事是检查链表是否有环
第二件事是寻找链表的入口

1. 检查链表是否有环如环形链表I一样，通过快慢指针来实现，当快指针的next和next.next不为null的时候就一直进行while循环，快指针一次走两步，慢指针一次走一步，如果快慢指针相遇则说明有环，否则无环；
2. 寻找链表入口涉及到一个巧妙的数学证明，这个数学证明的结论是：当快慢指针相遇后，定义一个指针从头节点出发，同时一个指针从快慢指针相遇处出发，当这两个指针相遇的时候，就代表走到了环形链表的入口处，这个数学证明如下图，应试的话记结论就行：

代码

/*** 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) {ListNode slowNode = head;ListNode fastNode = head;while (fastNode != null && fastNode.next != null) {slowNode = slowNode.next;fastNode = fastNode.next.next;if (slowNode == fastNode) {ListNode cur = head;while (cur != slowNode) {cur = cur.next;slowNode = slowNode.next;}return cur;}}return null;}
}