Li Kou interview question 02.08 Loop detection

subject

Given a linked list , If it is a linked list , Implement an algorithm to return to the beginning node of the loop . If the ring does not exist , Please return null.

If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , We use integers pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list .

Example

Input ：head = [3,2,0,-4], pos = 1
Output ：tail connects to node index 1
explain ： There is a link in the list , Its tail is connected to the second node .

Input ：head = [1,2], pos = 0
Output ：tail connects to node index 0
explain ： There is a link in the list , Its tail is connected to the first node .

Input ：head = [1], pos = -1
Output ：no cycle
explain ： There are no links in the list .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/linked-list-cycle-lcci
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1： Speed pointer

1、 Find the meeting point first

2、 Find the starting point of the ring

Java Realization

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

		// Find a meeting point 
        while (fast != null && fast.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        if (fast == null || fast.next == null) return null;

		// Starting point of ring finding 
        slow = head;
        while (fast != slow) {
    
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}