【环形链表】 判断环形？ 返回入环节点？ 两种问题具体思路，文中包含多种解法（附完整代码）

前言

本文将介绍两种环形链表的问题——判断环形链表 和 返回入环节点

对于这两个问题，都将各自介绍两种不同的思路方法。

【暴力法】【双指针】

【哈希遍历】【快慢指针】

一、环形链表是什么？

环形链表是一种特殊的链表结构，其中至少存在一个节点，它的指针指向链表中的其他节点，从而形成一个环状。

二、环形链表Ⅰ（判断环形链表）

在这里我们引入具体的题目，方便大家更好地理解环形链表问题。

题目链接: [点击链接] Leetcode 141. 环形链表

这一类环形链表问题，要求给出头节点，判断是否为环形链表即可。

1.方法一（暴力）

这道题很有趣，并且值得注意的是给出了节点数量的范围。

既然给出了节点数，那么我们就可以利用环形链表的特点（有进无出），来进行循环，环形链表一旦开始循环，就无法自己跳出循环。

所以跳出循环的就不是环形链表。

代码如下：

class Solution {
   
public:
    bool hasCycle(ListNode *head) {
   
       for(int i=0;i<=10000;i++){
   //这里i<=10000是因为节点最多有10000个
            if(head==nullptr){
   
                return false;
            }
            head=head->next;
        }
        return true;
    }
};

2.方法二（双指针）

可以采用快慢指针的方式，将链表的所有节点全部走过，一旦，两个指针再相遇，说明为环形链表。

快慢指针主要利用，慢指针每次移动慢，快指针每次移动快，如果是非环形的链表，那么快指针会一直比慢指针快，如果最初快指针就在慢指针前面，那么两个指针将永不相遇。

反之，如果两个指针相遇了说明了什么呢？

说明链表是环形的，快指针又回到了慢指针的后面。

代码如下：

class Solution {
   
public:
    bool hasCycle(ListNode* head) {
   
        ListNode* slow = head;//慢指针
        ListNode* fast = head;//快指针
        while (fast && fast->next) {<