Leetcode 0141. circular linked list - three solutions

【LetMeFly】 There are three ways to solve ：141. Circular list

Force button topic link ：https://leetcode.cn/problems/linked-list-cycle/

Give you a list of the head node head , Judge whether there are links in the list .

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 ）. Be careful ：pos Not passed as an argument  . Just to identify the actual situation of the linked list .

If there are rings in the list  , Then return to true . otherwise , return false .

 

Example 1：

 Input ：head = [3,2,0,-4], pos = 1
 Output ：true
 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 ：true
 explain ： There is a link in the list , Its tail is connected to the first node .

Example 3：

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

 

Tips ：

• The number range of nodes in the linked list is [0, 104]
• -105 <= Node.val <= 105
• pos by -1 Or one of the lists Valid index .

 

Advanced ： You can use O(1)（ namely , Constant ） Does memory solve this problem ？

Method 1 ： Hashtable

The principle is simple , Traversing the linked list , Record the traversed nodes with a hash table .

During traversal , If you find that a node already exists in the hash table , It means that this node has been traversed , in other words Ring

Once traversed “next It's empty ” Some node of , It shows that this node is the last node of the linked list , in other words acyclic

• Time complexity $O(n)$, among $n$ Is the number of nodes in the linked list .C++ If you use unordered_set, Then the complexity of inserting and judging whether it exists is $O(1)$
• Spatial complexity $O(n)$

AC Code

C++

class Solution {
    
public:
    bool hasCycle(ListNode *head) {
    
        unordered_set<ListNode*> se;
        while (head) {
    
            if (se.count(head))
                return true;
            se.insert(head);
            head = head->next;
        }
        return false;
    }
};

Method 2 ： Speed pointer

The reason is not difficult , With two Pointers , The initial positions point to the chain header node .

Each time the fast pointer moves back two nodes , The slow pointer moves one node backward .

If the fast pointer moves to the end of the linked list , It means that the linked list has no ring

If the fast and slow hands meet , It means that the linked list has links

** Be careful ：** If there is a ring , Then the fast and slow hands will meet . Because the fast pointer must enter the ring ahead of the slow pointer , Wait for the slow pointer to enter the ring , The fast pointer will catch up with the full pointer （ Because the speed is twice that of the slow pointer ）, And I will not jump directly without meeting （ The old position before the slow pointer moves and the new position after it moves $2$ Nodes , Go ahead at one time $2$ Nodes , Must step on one ）

• Time complexity $O(n)$, among $n$ Is the number of nodes in the linked list . The speed of a slow pointer is half that of a fast pointer , The fast pointer will catch up with the slow pointer in two laps
• Spatial complexity $O(1)$

AC Code

C++

class Solution {
    
public:
    bool hasCycle(ListNode *head) {
    
        if (!head)
            return false;
        ListNode *fast = head, *slow = head;
        do {
    
            if (!fast->next || !fast->next->next) {
      //  It's the end 
                return false;
            }
            fast = fast->next->next;
            slow = slow->next;
        } while (fast != slow);
        return fast == slow;
    }
};

Method 3 ： Pass the question for the sake of passing the question

This method is not practical , But you can pass the question with short code .

The title says that the maximum length of the linked list is $10^4$, So we can count while traversing the linked list , If the number of nodes exceeds $10^4$, It means that a node has been traversed more than once , That is to say, there are links in the linked list .

• Time complexity $O(n\vee C)$, among $n$ Is the number of nodes in the linked list .$C$ Is the maximum number of nodes in the linked list （ The title is $10^4$）
• Spatial complexity $O(1)$

AC Code

C++

class Solution {
    
public:
    bool hasCycle(ListNode *head) {
    
        int count = 0;
        while (head) {
    
            count++;
            if (count > 10000)
                return true;
            head = head->next;
        }
        return false;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/126017056