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

进阶：
你能否不使用额外空间解决此题？

 

 

 

//章节 - 链表    
//二、双指针技巧
//1.环形链表
/*
算法思想：
    想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。
这正是我们在链表中使用两个速度不同的指针时会遇到的情况：如果没有环，快指针将停在链表的末尾。如果有环，快指针最终将与慢指针相遇。
*/
//算法实现：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return false;
        ListNode *fast = head, *slow = head;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;    //快指针，每次移动两步
            slow = slow->next;  //慢指针，每次移动一步
            if (fast == slow)   //快慢指针相遇，说明有环
                return true;
        }
        return false;
    }
};