【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;
    }
}