Force buckle 142 Circular linked list II

Cattle guest ：NC3

Given a linked list , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

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 It's just for identifying rings , It's not passed to the function as an argument .

explain ： It is not allowed to modify the given linked list .

Advanced ：
Can you use O(1) Space to solve this problem ？

Method 1 ： Hashtable

Ideas and algorithms

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 .

Code

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 and algorithms

1. The speed pointer determines whether there is a ring
   One pointer at a time +1; One pointer at a time +2, If we meet , There are rings .
2. Directly determine the entrance location
   Tell me where the pointer gets its head , The slow pointer is the last position （ Meeting point ） Then define ptr Every time +1,
   Meeting again is the entrance

class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
    
            slow = slow->next;
            if (fast->next == nullptr) {
    
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
    
                ListNode *ptr = head;
                while (ptr != slow) {
    
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        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 ,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). Use only the slow,fast,ptr Three pointers .

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/