算法题：判断链表是否是环形链表

前段时间被问到一个面试题，如何判断一个链表是否是环形链表。

碰到这个问题，我觉得挺逗的，印象里刷过，应该是leetcode上的原题。我当时奔着分析的思路，想了下，这个直接说结果太草率了，倒不如聊聊过程。

首先，链表这个概念是不是知道，大概是一个类似下边的数据结构

struct ListNode{
    Node *next;
    int data;
};

其次，环的问题。这个环，怎么计算呢？我的想法是做个记录，往后遍历，找到之前存储过的记录，就判断有环。代码大概如下：

bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
}

我觉得是OK的，事后，我看了下leetcode刷题记录，应该还用过快慢指针法，代码如下：

 bool hasCycle(ListNode *head) {
        //两个运动员位于同意起点head
        ListNode* faster{ head };  //快的运动员
        ListNode* slower{ head };  //慢的运动员

        if (head == NULL)  //输入链表为空，必然不是循环链表
            return false;

        while (faster != NULL && faster->next != NULL) {
            faster = faster->next->next;  //快的运动员每次跑两步
            slower = slower->next;  //慢的运动员每次跑一步
            if (faster == slower)  //他们在比赛中相遇了
                return true;  //可以断定是环形道，直道不可能相遇
        }
        return false;  //快的运动员到终点了，那就是直道，绕圈跑不会有终点
}

其实，只是看起来代码有点多，原理懂了，适用范围还挺广的。加油，送给还在学习的你！