LeetCode題目鏈接

題目：

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

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

答案：

/**
 * 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) {
        ListNode *slow = head;
        ListNode *fast = head; 
        while (slow != NULL && fast != NULL && fast->next != NULL) {
            
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};

解析：

題目要求：判斷鏈表中是否存在環(huán), 并且不借助額外空間。

最開始的想法是記錄指針的路線，然后比對。但是不滿足要求。
可以思考能否使用兩個指針來遍歷。網(wǎng)上有一種思路是快慢指針。一個指針每次走一步，另一個指針每次走兩步。如果存在環(huán)，那么兩個指針都必然會出現(xiàn)死循環(huán)，由于兩個速度不一樣，如果出現(xiàn)指針的值相等，那么就可以判斷出現(xiàn)死循環(huán)了。如果直到結(jié)束都不出現(xiàn)，那么說明不存在環(huán)。