[LeetCode] 142. Linked List Cycle II, Medium

2025. 3. 14. 12:43·CodingTest/LeetCode
반응형

1. 문제

  • 연결 리스트 head가 주어질 때, 사이클의 시작 노드를 반환하라. 
  • pos는 주어지지 않는다.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let faster = head, slower = head;
    
    while(faster && faster.next) {
        slower = slower.next;
        faster = faster.next.next;
        
        if(slower === faster) {
            faster = head;

            while(faster !== slower) {
                faster = faster.next;
                slower = slower.next;    
            }
            return faster;
        }
    }
    
    return null; 
};
  • 141번 문제와 마찬가지로 토끼 거북이 알고리즘을 사용한다.
  • 원리는 처음에는 토끼를 2칸, 거북이를 1칸씩 이동하다가 만나는 순간, 토끼를 시작점으로 보내서 1칸 씩 이동시키면 사이클의 시작점에서 만나게 되는 것.
  • 채찍피티의 간단한 증명

  • 요약하면, 시작점부터 사이클 시작 까지의 거리 = 만난 시점에서 사이클 시작 까지의 거리 이므로, 토끼를 시작점으로 보내서 거북이랑 똑같이 한 칸씩 이동 시키다가 만나는 곳이 사이클의 시작지점이 된다.

 

저작자표시 (새창열림)
'CodingTest/LeetCode' 카테고리의 다른 글
  • [LeetCode] 19. Remove Nth Node From End of List, Medium
  • [LeetCode] 160. Intersection of Two Linked Lists, Easy
  • [LeetCode] 141. Linked List Cycle, Easy
  • [LeetCode] 707. Design Linked List, Medium
뜸부깅
뜸부깅
코딩에 대한 여러 개인적인 생각을 정리하고 공부를 하는 공간입니다!!
  • 뜸부깅
    코오오딩
    뜸부깅
  • 전체
    오늘
    어제
    • Note (429)
      • Skill (31)
        • Java & Spring (9)
        • Javascript & HTML & CSS (0)
        • React (0)
        • Next.js (22)
      • CodingTest (389)
        • 백준 온라인 저지(BOJ) (140)
        • 프로그래머스(Programmers) (79)
        • LeetCode (170)
      • Algorithm & Data Structure (6)
      • [Project] 포트폴리오 (3)
        • Front end (3)
        • Back end (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    BOJ
    백준2751
    Easy
    백준1260
    leetcode 2236
    TypeScript
    백준
    component-scan
    백준7576
    백준7576자바
    자바
    medium
    백준1427
    meidum
    프로그래머스
    boj2108
    Java
    알고리즘
    boj1427
    next 14
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
뜸부깅
[LeetCode] 142. Linked List Cycle II, Medium
상단으로

티스토리툴바