C++ 链表有环问题解决_链表有环怎么处理

前段时间美团二面，考察了我链表有环的问题，我虽然以前看牛客网也注意到有的面试官考察过链表有环的问题，但是我一直属于蒙圈的状态，链表有环，那不就是出不来了吗，该怎么办？
现在我认真重复一下问题：是这样的，如何判断一个链表中有环？
面试那天，我给面试官的回答是可以使用map,第一次出现，map的值默认是0，改这个值，改为1什么的，当碰到1的时候就知道有环了。至于为什么map的值默认是0，我现在也不知道，当然，在面试官的提醒下，我还是写出来了这道题，还是比较开心的。
以下是C++代码：可以参考以下。

#include<iostream>
#include<map>
using namespace std;
struct Node{
   int val;
   Node * next=nullptr;
};
class Solution
{
public:
   map<Node*,Node*> deal;
   bool Has_loop(Node* node)
   {
      if(node==nullptr||node->next==nullptr)
      return false;
      Node* p=node;
      while(p)
      {
      
      if(deal[p]!=0)
      {
         return ture;
      }
        deal[p]=p;
        p=p->next;
      }
      
   }
};
int main()
{
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

下面的是面试官最想要的答案，快慢指针。
原理是这样的，进行一次遍历，一个是快指针，一个是慢指针。如果链表中没有环，那么慢指针是永远追不上快指针的。但是如果存在环的话，那么就会像时钟那样，尽管转动的速度是不一样的，但是总是会碰在一起的。下面是我的代码：

class Solution{
 public:
  bool_hasloop(Node* node)
  {
     if(node==nullptr||node->next==nullptr)
      return false;
    
    Node* fast,second;
    fast=node;
    second=node;
    while(fast&&fast->next)
    {
        second=second->next;
        fast=fast->next->next;
        if(fast==second)
        return true;
    }
    return false;
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

顺便补充一下，判断环的长度。

int GetLoopLength(Node* head)
{
    Node *slow = head, *fast = head;
 
    while ( fast && fast->next )
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast )//第一次相遇
            break;
    }
    slow = slow->next;
    fast = fast->next->next;
    int length = 1;       //环长度
    while ( fast != slow )//再次相遇
    {
        slow = slow->next;
        fast = fast->next->next;
        length ++;        //累加
    }
    return length;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

好了，我们先介绍到这里。