#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
typedef int ElemType;
typedef struct LinkNode
{
    ElemType data;
    LinkNode *next;
}LinkList;
LinkNode* Init_LinkNode()
{
    LinkNode *head = (LinkNode*)malloc(sizeof(LinkNode));
    head->next = nullptr;
    head->data = 0; //存储链表长度
    return head;
}
void Create_LinkNode(LinkNode *head)
{
    //头插法
    LinkNode *p = head,*s,*q=head;
    cout<<"please input the sequence:";
    ElemType x;
    cin>>x;
    while (x != 999)
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));
        s->data = x;
        s->next = head->next;
        p->next = s;
        p->data++;
        //q指针是为了找到末尾指针,建立环
        q->next=s;
        q=s;
        cin>>x;
    }
    //建立环
    q->next = head->next;
}
//判断环形链表方法1.哈希表方法
bool has_Cycle(LinkNode *head)
{
    unordered_set<LinkNode*> seen;
    LinkNode *p = head->next;
    while(p)
    {
        if (seen.count(head))
            return true;  //哈希表中有表示有环
        seen.insert(head);  //插入哈希表
        p = p->next;
    }
    return false;
}
bool has_cycle(LinkNode *head)
{
    //双指针判断单链表中是否有环,慢指针每次走1步,快指针走每次走两步,有环走表长次一定相遇
    LinkNode *fast = head->next,*slow = head->next;
    while (slow && fast && fast->next)
    {
        if (slow == fast)
        {
            cout<<"单链表长度为:"<<head->data<<endl;
            return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}
void show(LinkNode *head)
{
    LinkNode *p = head->next;
    while (p)
    {
        cout<<p->data<<endl;
        p = p->next;
    }
}
int main()
{
    LinkNode *head = Init_LinkNode();
    Create_LinkNode(head);
//    show(head);
    if (has_Cycle(head))
        cout<<"有环\n";
    else
        cout<<"无环"<<endl;
    if (has_cycle(head))
        cout<<"有环\n";
    else
        cout<<"无还"<<endl;
    return 0;
}