[summary of linked list skills] 141. Circular linked list (simple)

Circular list （ Simple ）

One 、 subject

Given a linked list , 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 , 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 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 .

Advanced ：

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

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  

Two 、 Problem solving

/**
 * 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) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                return true;
        }
        return false;
    }
};

 author ：shazi2925
 link ：https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-jian-dan-by-shazi292-mijg/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .