题目链接：Linked List Cycle

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

Follow up:

Can you solve it without using extra space?

这道题的要求是判断一个链表中是否有环。

设置两个指针fast和slow，初始值都指向头指针，slow每次前进一步，fast每次前进两步。如果存在环，则fast必先进入环，而slow后进入环，两个指针必定相遇（当然，fast先到达尾部为NULL，则为无环链表）。

由于slow每次向前1步，fast每次向前2步，用相对运动的观点来看，把slow看作静止，那么fast每次相对slow向前1步，二者在顺时针方向上的距离每经过一个时刻就减少1，直到变为0，也即二者恰好相遇。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        if(head == NULL || head -> next == NULL)
            return false;
        
        ListNode *s = head, *f = head;
        while(f != NULL && f -> next != NULL)
        {
            s = s -> next;
            f = f -> next -> next;
            
            if(f == s) // f和s相遇，说明有环
                return true;
        }
        
        return false;
    }
};