[leetcode] #141 Linked List Cycle

[leetcode] #141 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?
O(1)空間を用いて,単一チェーンテーブルにループが存在するか否かを判断する.
問題解決の考え方:
1、fastポインタは2歩、lowポインタは1歩2、ループ後、ループがあればfastポインタがlowポインタに追いつく瞬間がある.
なぜ3歩ではなく2歩歩くのかについては、4歩fastポインタは毎回lowポインタより1歩多く、ループがあれば、最初の差がnであると仮定します.毎回1歩縮小し、差が0の場合、自然に両者が重なり、3歩、4歩歩き、nが(3-1)または(4-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) {
        ListNode *low = head;
        ListNode *fast = head;
        while (low && fast && fast->next) {
            low = low->next;
            fast = fast->next->next;
            if (low == fast) {
                return true;
            }
        }
        return false;
    }
};