判断单链表是否成环

学习数据结构的链表，课上提出了一个问题：如何判断一个单链表是否成环？基于上次学习的快慢指针算法，可以给出一种快速判断的方法：仍然采用快慢指针，当单链表成环状的时候，快慢两个指针一定会相遇（追击问题，操场上落后的你一定会再次与朋友相遇，只要你跑的足够慢！！）

//判断单链表里面是否有环?
//1.生成一个单链表，然后人为的成环
//2.用两种方法判断单链表里面是否存在环?

#include<iostream>
using namespace std;

//定义结点
struct ListNode
{
   
    int val;
    ListNode* next;
    ListNode() : val(), next() {
   } //
    ListNode(int x) : val(x), next(NULL) {
   } //
};
//生成单链表，数据初始化为1,2,3...,尾节点指向第三个结点
ListNode *GenerateList(int num)
{
   
    ListNode* head=new ListNode(1);
    ListNode* curNode=head;
    for(int i=1;i<num;++i)
    {
   
        curNode->next=new ListNode(i+1);
        curNode=curNode->next;
    }
    curNode->next=head->next->next;
    return head;
}
//判断是否存在环，用快慢指针
bool ifloop(ListNode* head)
{
   
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast->next)
    {
   
        if(fast->next->next)
        {
   
            fast=fast->next->next;
            slow=slow->next;
        }
        else 
        {
   
            fast=fast->next;
            slow=slow->next;
        }
        if(fast==slow)
        return true;

    }
    return false;

}


int main()
{
   
    cout<<"输入单链表长度";
    int num;
    cin >>num;
    ListNode* ListA=GenerateList(num);
    cout<<ifloop(ListA);
    return 0;
}

程序运行结果

**

记住链表创建完毕后，不要手欠打印出来，不信你试试！！

**