[leetcode 75] 142. Linked List Cycle II

문제해석

linked list의 head가 주어졌을 경우 순환이 시작되는 노드를 반환, 만약 순환의 없다면 null을 반환

 

순환되는 노드는 주어진 노드 내부에 위치하며

내부적으로 pos는 순환되는 노드의 시작 위치를 말하며 (파라미터로 전달되지 않음) 순번은 0부터 시작함

 

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }

    Set<ListNode> nodes = new HashSet<>();
    ListNode node = head;
    while (node != null) {
        if (nodes.contains(node)) {
            return node;
        }
        nodes.add(node);
        node = node.next;
    }

    return null;
}

 

Follow up에 메모리는 O(1)만 사용해서 풀 수 있는지를 물어보는데

찾아보니 토끼와 거북이 알고리즘이라는게 있다고 한다.

나중에 보충이 필요한 내용