3.5

main.py

"""
# 문제 : 순환 검출 (Cycle Detection)

- 주어진 연결 리스트가 순환을 가지는지 판단하는 프로그램을 작성하라
- 순환이라고 하면, 특정 노드를 기준으로 이전 특정 노드로 돌아가 순환이 생기는
 경우라고 보면 된다.

## 아이디어 (Brute-force)

1. 노드를 순회한다.
  - 순회 중 노드가 끝에 도달하거나 연결이 없으면 종료
  - 현재까지 순회 카운터를 기록
  - 노드를 처음부터 순회한다. (순회 카운터 만큼)
    - 바깥 순회에서 선택된 노드와 비교해 2번 겹친다면 순환이 발생
    - 아니라면 순회를 종료한다.

시간 복잡도 : O(n^2)
공간 복잡도 : O(1)

## 아이디어 (해시 테이블)

1. 노드를 순회한다.
  - 각 노드를 set으로 있는지 없는지를 확인한다.
  - 있다면 참(true)를 반환
  - 없으면 set에 추가한다.

시간 복잡도 : O(n)
공간 복잡도 : O(n), 해시 테이블에 최악의 경우 모든 노드를 저정한다.

## 아이디어 (Two pointer)
1. slow, fast 포인터는 head를 가리킨다.
2. slow 는 1번의 이동을 한다.
3. fast 는 2번의 이동을 한다.
4. fast 와 slow 가 같아진다면 연결리스트는 순환이다.
5. fast 나 slow 가 가리키는 노드가 None이면 순환은 없다.

시간 복잡도 : O(n)
공간 복잡도 : O(1)
"""


class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def hasCycle(head: Node) -> bool:
    outer = head

    node_cnt = 0

    while outer and outer.next:
        outer = outer.next
        node_cnt += 1

        visit = node_cnt
        inner = head

        matched = 0

        while visit > 0:
            if outer != inner:
                inner = inner.next

            if outer == inner:
                matched += 1

            if matched == 2:
                return True

            visit -= 1

    return False


def hasCycle2(head: Node) -> bool:
    curr = head
    node_set = set()

    while curr:
        if curr in node_set:
            return True

        node_set.add(curr)
        curr = curr.next

    return False


def hasCycle3(head: Node) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True
    return False


if __name__ == '__main__':
    node11 = Node(11)
    node12 = Node(12)
    node13 = Node(13)
    node14 = Node(14)
    node15 = Node(15)

    node11.next = node12
    node12.next = node13
    node13.next = node14
    node14.next = node15
    node15.next = node13

    print(hasCycle(node11))