leetcode刷题日记:141. Linked List Cycle（环形链表）

这一题是给我们一个链表让我们判断这是否是一个环形链表，我们知道如果一个链表中有环的话这一个链表是没有办法访问到尾的，
假若有如图所示的带环链表：

我们从图示中很容易看出来这一个链表在访问的时候会在里面转圈，我们再来看看无环链表的访问是什么样的，

我们可以清楚的看到，这一个无环链表在访问的时候会访问到尾，最后指针为NULL，此时说明链表无环。但是还是无法区别这两种链表啊，因为假如链表够长，我怎么知道它是因为链表有环导致没有访问完，还是因为链表太长没有访问完，所以根据链表经过的节点数目是无法判断这是一个有环链表还是无环链表。
但是我们一想有环链表啥特性，是不是访问结点时会重复，既然一个指针访问链表时无法判断是不是重复访问了，那么我们用两个指针去看会不会重复访问结点不就行了，就像我们跑步一样，在环形跑道上只要两个人的速度不一样这两个人就会相遇，这两个指针也是这样只要两个指针的速度不一样，在环上就会相遇。如果链表无环，跑的快的指针会先一步到达链表的尾端，这样就可以判断这是一个无环链，综上，使用两个遍历速度不一样的指针可以判断出一个链表是否为有环链表。
就像钟表上的时针与分针会相遇一样，这两个速度不一样的指针也会相遇。
根据上面的思路我们可以写出如下代码:

bool hasCycle(struct ListNode *head) {
    struct ListNode *p=head, *q = head;
    if(p!=NULL){
        p = p->next;
    }
    while(p!=q&&p!=NULL&&q!=NULL){
        p=p->next;
        if(p!=NULL){
            p=p->next;
        }
        q=q->next;
    }
    if(p==NULL){
        return false;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果截图：