Leetcode circular linked list (fast and slow pointer) code line by line interpretation

Preface

The judgment of circular linked list is a classical problem in algorithm learning , This article will explain and use the code to explain how to judge the circular linked list through the speed pointer .

subject

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 ：

 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 .

Link to the original topic ：https://leetcode-cn.com/problems/linked-list-cycle

solution - Speed pointer

Specific ideas ： Create two pointers , A quick pointer , A slow pointer , Both pointers initially point to the chain header node . The fast pointer moves back two nodes at a time , The slow pointer moves back one node at a time . If the linked list has a ring , Then the fast and slow hands will meet . If the linked list has no ring , Then the fast pointer will go to the end of the linked list first .

Algorithm flow ：

• Special judgement ： If the chain header node head Null pointer , Then return directly false

• Create a fast pointer , A slow pointer , Are initialized as chain header nodes

• Traversing the linked list , Exit when the fast pointer is empty

  • The fast pointer goes back one node first , If the node is not empty , Then go back one node

  • Slow the pointer back one node

  • If the speed pointer is equal , And are not empty , Indicates that the speed pointer meets , The list has rings , return true

• If you traverse the linked list normally , It indicates that the linked list has no rings , return false

Code implementation ：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    bool hasCycle(ListNode *head) {
    
        //  Special judgement ： If the chain header node head Null pointer , Then return directly false
        if(head == NULL) return false;
        //  Create a fast pointer , Initialize to the chain header node 
        ListNode *fast = head;
        //  Create a slow pointer , Initialize to the chain header node 
        ListNode *slow = head;
        //  Traversing the linked list , Exit when the fast pointer is empty 
        while(fast != NULL){
    
            //  The fast pointer goes back one node first 
            fast = fast->next;
            //  If the node is not empty , Then go back one node 
            if(fast != NULL) fast = fast->next;
            //  Slow the pointer back one node 
            slow = slow->next;
            //  If you traverse the linked list normally , It indicates that the linked list has no rings , return false
            if(fast == slow && fast != NULL) return true;
        }
        //  If you traverse the linked list normally , It indicates that the linked list has no rings , return false
        return false;
    }
};