141. Linked List Cycle

---

문제 분석

링크드 리스트의 헤드가 주어질 때 이 링크드 리스트가 순환한다면 true, 아니라면 false를 리턴하라

---

풀이 과정

단일 연결 링크드 리스트는 노드가 다음 노드만 가리킬 뿐
누가 나를 가리키는 지 알 수 없다.
해당 조건에서 순환을 하는지 찾는 문제이다.

여기서 말하는 순환의 이해를 n번 노드 이후 탐색을 하다가 다시 n번 노드에 도착한다면 순환이라 판단했다.
탐색을 위한 2개의 탐색 인덱스를 둔다.
하나는 천천히 탐색하는 인덱스
하나는 빠르게 탐색하는 인덱스
토끼와 거북이 알고리즘을 선택하였다.

무조건 만나는 보장이 될 경우 해당 알고리즘을 사용할 수 있다.
n번 노드의 탐색을 시작으로 다시 n번이 도착하지 않는 경우(null일 경우)는 false를 리턴한다.

재귀적으로 풀었다. 아래는 순차적인 로직을 말로 설명해보겠다.

1. head(first)와 head.next(second)를 매개변수로 재귀적인 탐색을 시작한다.
2. 만약 둘 중 하나가 null 이라면 다음 노드가 존재하지 않는다는 뜻이기 때문에 false를 리턴한다.
3. 두 헤드의 다음 넥스트가 null 이라면 다음 노드가 존재하지 않는다는 뜻이기 때문에 false를 리턴한다.
4. 두 헤드가 같다면 true를 리턴한다.
5. (재귀적인 탐색) 느린 탐색을 하는 first.next 와 빠른 탐색을 하는 second.next.next를 매개변수로 넘긴다.

---

나의 생각

링크드 리스트라는 자료구조에 초점이 맞추어지다보니 처음에 문제를 이해하지 못하였고 로직도 떠오르지 않았다.
해당 문제를 이해하기 위해 다른 분들의 풀이를 참고하고 주변 스터디분에게 도움을 받았다.
그렇게 문제를 풀다보니 요구사항을 이해할 수 있었다.
재귀적으로 풀지 않고 반복문으로 풀었다면 공간복잡도를 조금 더 아낄 수 있을 것 같다.

---

코드

    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        return findNode(head, head.next);
    }

    public boolean findNode(ListNode first, ListNode second) {
        if (first == null || second == null) return false;
        if (first.next == null || second.next == null) return false;
        if (first == second) return true;

        return findNode(first.next, second.next.next);
    }