[LeetCode]Linked List Cycle

[LeetCode]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?

這道題是要求在不額外使用存儲空間的基礎上判斷一個單鏈表中是否存在一個環。

環的存在，就是在無環的基礎上，將最後一個結點的next不設為NULL，而是指向該結點前的任意一個結點，所以包含環的單鏈表就沒有“最後一個結點”的說法了。

思路很容易想到，設兩個指針，slow 與 fast。
1. 兩個指針移動的速度不同，後者是前者的兩倍。
2. 若鏈表無環，則fast最後一定為NULL
3. 若鏈表有環，則 slow 與 fast一定會有指向同一個結點的時刻。

下面貼上代碼：

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