Linked list - 142. Ring linked list II

1 Title Description

142. Circular list II

Given the head node of a linked list head , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to 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 , The evaluation system uses an integer 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 .
No modification allowed Linked list .

2 Title Example

3 Topic tips

• The number of nodes in the list is in the range [0, 104] Inside
• -105 <= Node.val <= 105
• pos The value of is -1 Or a valid index in a linked list

4 Ideas

Method 1 ： Hashtable
A very intuitive idea is ： We iterate through each node in the linked list , And write it down ; Once you encounter a node that has been traversed before , You can determine that there is a link in the linked list . With the help of hash table, it is very convenient to realize .
Complexity analysis

Time complexity ：O(N)O(N), among NN Is the number of nodes in the linked list . We just need to access every node in the linked list .

Spatial complexity ：O(N)O(N), among NN Is the number of nodes in the linked list . We need to save each node in the linked list in the hash table .

Method 2 ： Speed pointer
We use two pointers ,fast And slow. They all start at the head of the linked list . And then ,slow The pointer moves back one position at a time , and fast The pointer moves back two positions . If there are rings in the list , be fast The pointer will end up with slow The pointer meets in the ring .

As shown in the figure below , Let the length of the outer part of the link in the linked list be aa. slow After the pointer enters the ring , Gone again bb The distance between fast meet . here , fast The pointer has gone through the ring nn circle , So the total distance it has traveled is a+n(b+c)+b=a+(n+1)b+nc.

According to the meaning , Anytime , fast The distance traveled by the pointer is slow Pointer 22 times . therefore , We have

a+(n+1)b+nc=2(a+b)*a=c+(n−1)(b+c)

With a=c+(n-1)(b+c) The equivalence of , We will find that ： The distance from the meeting point to the entry point plus n−1 Ring length of circle , Exactly equal to the distance from the head of the linked list to the ring entry point .

therefore , If I found slow And fast When we met , Let's use an extra pointer ptr. start , It points to the head of the linked list ; And then , It and slow Move back one position at a time . Final , They will meet at the entry point .

Complexity analysis

Time complexity ：O(N)O(N), among NN Is the number of nodes in the linked list . In the initial judgment of whether the fast and slow pointers meet ,\textit{slow}slow The distance traveled by the pointer will not exceed the total length of the linked list ; Then when looking for the entry point , The distance traveled will not exceed the total length of the linked list . therefore , The total execution time is O(N)+O(N)=O(N)O(N)+O(N)=O(N).

Spatial complexity ：O(1)O(1). We only used \textit{slow}, \textit{fast}, \textit{ptr}slow,fast,ptr Three pointers .

5 My answer

public class Solution {
    
    public ListNode detectCycle(ListNode head) {
    
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
    
            if (visited.contains(pos)) {
    
                return pos;
            } else {
    
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

public class Solution {
    
    public ListNode detectCycle(ListNode head) {
    
        if (head == null) {
    
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
    
            slow = slow.next;
            if (fast.next != null) {
    
                fast = fast.next.next;
            } else {
    
                return null;
            }
            if (fast == slow) {
    
                ListNode ptr = head;
                while (ptr != slow) {
    
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}