Leetcode No.141 *

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

                      

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

               

解答:有一种方法是直接赋值的方法,对所有搜寻的节点值进行赋值。如果得到当前的节点值与所赋值相同,则为有环链表。但这样做一个最大的问题是破坏了原有链表,所有并不可取。

通过查看博客,这是一道快慢指针的算法。通过构建两个指针,慢指针一次执行一步,快指针一次执行两步,若最后相等,那么是有环链表。

代码如下:

//141
bool hasCycle(ListNode *head)
{
    ListNode* fast, *slow;
    if(head==NULL) return false;
    fast = head->next;
    slow = head;
    while(fast!=slow)
    {
        if(fast==NULL || fast->next==NULL) return false;
        fast = fast->next->next;
        slow = slow->next;
    }
    return true;
}//141
原文地址:https://www.cnblogs.com/2Bthebest1/p/10851071.html