jd0208.环路检测

题目描述

给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

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

题解

快慢指针

整体思路：

1. 检测有没有环，使用快慢指针slow和fast（一次走两步）；
2. 找位置，当找到环之后，slow从head出发，fast从相遇点出发，一次都走一步，再次相遇为环的入口点

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    while (fast!=null&&fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
        if (slow==fast)
            break;
    }

    if (fast==null||fast.next==null)
        return null;

    slow = head;

    while (slow!=fast){
        slow = slow.next;
        fast = fast.next;
    }

    return slow;

}