[LeetCode] Linked List Cycle

🧑‍💻 언어 및 제출 결과

• 사용 언어: TypeScript
• 통과 여부: ✅

🧠 풀이 설명

첫 번째 풀이

function hasCycle(head: ListNode | null): boolean {
  try {
    JSON.stringify(head);
    return false;
  } catch (error) {
    if (error instanceof TypeError && error.message.includes("Converting circular structure to JSON")) return true;
    throw error;
  }
}

순환 리스트와 일반 리스트를 생성해서 시각화 하려고 했는데 애초에 순환 리스트는 JSON으로 변환 할 때 에러를 뱉더군요

TypeError: Converting circular structure to JSON

그래서 그냥 boolean을 뱉으면 되겠지만 이건 좀 ,, 그래서 다른 풀이도 작성 했습니다.

---

두 번째 풀이

function hasCycle_2(head: ListNode | null): boolean {
  const visited = new Set<ListNode>();

  while (head) {
    if (visited.has(head)) return true;

    visited.add(head);
    head = head.next;
  }
  return false;
}

전체적으로 탐색하고 중복되면 true를 뱉으면 되기 때문에 Set을 사용해서 중복처리를 하면 될 것 같았습니다
visited라는 Set을 만들어서 탐색한 노드를 저장할 공간을 만들어 주고 head는 탐색한 노드를 가리키는 포인터 변수로 사용한 뒤,
계속해서 .next를 통해 탐색하고, 만약 중복 된다면 순환 리스트로 판별하여 true를 뱉어내게 했습니다.

📊 시간/공간 복잡도

✅ 어떠한 근거로 시간/공간 복잡도가 이렇게 나왔는지 설명해주세요.

첫 번째 풀이

시간 복잡도: O(n) - JSON.stringify가 모든 노드를 순회
공간 복잡도: O(n) - JSON 문자열 생성에 메모리 사용

두 번째 풀이

시간 복잡도: O(n) - 각 노드를 한 번씩 방문
공간 복잡도: O(n) - Set에 최대 n개 노드 저장

⚡️ 풀이의 속도와 메모리 등을 캡쳐해서 올려주세요.

첫 번째 풀이

두 번째 풀이