(Linked List, Easy) Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/

단방향 Linked List에서 사이클이 있는지 판단하는 문제같다.

일단 떠오르는건 HashSet을 써서 방문한 ListNode인지 판단할 수 있을 것 같은데
(hashCode(), equals() 미 오버라이드로 동일성 기준 해시 뽑힐듯)
그렇게 하는 경우 매우 쉽게 풀 수 있으므로 코드 따로 안적고 넘어간다.

문제에서 follow up으로 O(1) 공간복잡도로 풀 수 있는지 제시하고 있다.
모르겠어서 인터넷 찾아보니 Floyd's Tortoise and Hare 알고리즘이란게 있다.

이것은 두 개의 포인터를 두고, 각각 1칸과 2칸씩 이동하도록 하는데
어느 순간 둘이 만나게 된다면 사이클이 존재한다고 볼 수 있다는 것이다.

추가로 공식을 보면 토끼와 거북이 두 개의 포인터가 만난 위치부터 사이클 시작까지의 길이는 사이클 진입 직전의 길이와 동일하다는 결론이 나온다.

이를 통해 사이클의 길이도 잴 수 있는데, 토끼와 거북이 포인터가 만난 지점인 x를 토끼의 위치로 두고, 거북이는 리스트의 시작 지점으로 옮긴다.
그 후 둘 다 한 칸씩 움직여서 만나는 지점이 바로 사이클의 시작점이다.

이 때 거북이나 토끼 둘 중 하나를 기준으로 잡고 다시 만날 때까지 한 칸 씩 돌리면서 카운트를 증가시키는 방법으로 사이클의 길이도 잴 수 있다.

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return true;
            }
        }

        return false;
    }
}