Description

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

 

Solution

题目要求检测单链表是否有环路（包括局部环路）。

由于是单链表，如果链表的next指针存在指向NULL的情况，那就一定没有环路。同时，最多也只可能存在一个环。由于题目要求空间复杂度为O(1)，因此无法简单地记录没一个节点的地址再对比重复的思路。

但若存在环路，遍历时最终会在该环路中循环无法跳出。因此只要使用两个指针fast和slow，fast每次向前走两步，slow则走一步，且开始fast和slow都指向head。如果不存在环路的链表中，fast与slow不可能再次相遇，相反，若fast与slow再次相遇则说明存在环路。

需要注意的是fast指针每次连走两步需要先检验走一步后是否为空，否则会引起内存访问错误。显然，若fast走一步为空的情况说明链表无环路。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool hasCycle(ListNode *head)
    {
        if(head == NULL) return false;
        ListNode *slow = head, *fast = head;
        while(true)
        {
            slow = slow->next;
            if(fast->next)
            {
                fast = fast->next->next;
            }
            else
            {
                return false;
            }
            if(slow == fast) return true;
            if(slow == NULL || fast == NULL) return false;
        }
        return false;
    }
};