# LeetCode Easy 141. Linked List Cycle
tags: leetcode
問題
アイデア
連結リストが与えられたとき,循環がないかを返せという問題です.
追加の課題として これを$O(1)$のメモリで解くことがあります.
この問題は末尾の次のノードに今まで訪れたことがあるかを調べればよく,
解法1
既に通った経路の値を書き変えることで,通った地点を目印します.
この場合はListNode
のvalue
が変わるという問題があります.
計算量
連結リストのノードの数を$N$とします.
- 時間計算量
- $O(N)$
- 空間計算量
- $O(1)$
C++
/** * 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) return false; auto cur = head; while (cur) { if (cur->val == NULL) return true; cur->val = NULL; cur = cur->next; } return false; } };
解法2(Floyd's cycle-finding algorithm)
Floyd's cycle-finding algorithmを用いれば,val
を書き換えずに循環を探すことが可能です.
これは毎回2
度進むポインタと1
度しか進まないポインタを使います.
循環するならば,2つのポインタが同じノードを指すことを利用しています.以前同じアルゴリズムを使う問題を扱ったことが有ります.
計算量
- 時間計算量
- $O(N)$
- 空間計算量
- $O(1)$
C++
/** * 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 || !head->next) return false; auto slow = head; auto fast = head->next; while (slow != fast) { if (!fast || !fast->next) return false; slow = slow->next; fast = fast->next->next; } return true; } };