Leetcode (142) - circular linked list II

Leetcode（142）—— Circular list II

subject

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 .

Example 1：

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

Example 2：

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

Example 3：

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

Tips ：

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

Advanced ： Can you use $O(1)$ The algorithm of space complexity solves this problem ？

Answer key

Method 1 ： Hashtable

Ideas

​​   A very intuitive idea is ： We Traverse each node in the linked list , And write it down ; Once the node traversed before is encountered again , You can determine that there is a link in the linked list . With the help of hash table, it is very convenient to realize .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        unordered_set<ListNode *> visited;
        while (head != nullptr) {
    
            if (visited.count(head)) {
    
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

Complexity analysis

Time complexity ：$O(N)$, among $N$ Is the number of nodes in the linked list . We just need to access every node in the linked list .
Spatial complexity ：$O(N)$, among $N$ 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

Ideas

​​   We use the speed pointer ,$\text{fast}$ And $\text{slow}$. They all start at the head of the linked list . And then ,$\text{slow}$ The pointer moves back one position at a time , and $\text{fast}$ The pointer moves back two positions . If there are rings in the list , be $\text{fast}$ The pointer will end up with $\text{slow}$ The pointer meets in the ring , And It must meet before the slow pointer reaches the end of the linked list .

​​   As shown in the figure below , Let the length of the outer part of the link in the linked list be $a$.$\text{slow}$ After the pointer enters the ring , Gone again $b$ The distance between $\text{fast}$ meet . here ,$\text{fast}$ The pointer has gone through the ring $n$ circle , therefore Quick pointer $\text{fast}$ The total distance traveled is $a+n(b+c)+b=a+(n+1)b+nc$.

​​   According to the meaning , Anytime ,$\text{fast}$ The distance traveled by the pointer is $\text{slow}$ Pointer $2$ times . therefore , We have the following equation ：
$$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 ： Subtract from inner ring $b$ The length of 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 $\text{slow}$ And $\text{fast}$ When we met , Let's use an extra pointer $\text{ptr}$. start , It points to the head of the linked list ; And then , It and $\text{slow}$ Move back one position at a time . Final , They will meet at the entry point .

Why does the slow pointer meet the fast pointer before the first lap of the loop is completed ？

set up The length of the ring by $A$, When the slow pointer enters the ring, the position of the fast pointer in the ring $B$（ The value range is $[0,A-1]$）,
When the fast and slow hands meet [ The slow pointer walked in the ring $C$], Yes
C % A = ( B + 2C) % A, Equivalent to
$An+C=B+2C$, Merge to
$C=An-B$
When $n=1$ when , $0<=C<A$
so The slow pointer must meet the fast pointer before the first circle of the loop is completed

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
    
            slow = slow->next;
            if (fast->next == nullptr) break;
            else fast = fast->next->next;
            if (fast == slow) {
    
                fast = head;	//  At this point, the fast pointer is useless , Used as a temporary variable 
                while (fast != slow) {
    
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};

Complexity analysis

Time complexity ：$O(N), among $N$ Is the number of nodes in the linked list . In the initial judgment of whether the fast and slow pointers meet ,$\text{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)$.
Spatial complexity ：$O(1)$. We only used $\text{slow},\text{fast}$ Two pointers .