공간복잡도
-
CTCI | LoopAlgorithm/Linked List 2024. 4. 4. 21:03
Linked List에 있는 Loop을 찾아라 Linked List에 Cycle이 있을 수 있다. 이런 경우, 제일 첫번째 노드를 찾으라는 문제이다. 이 문제는 내가 가장 좋아하는 문제중 하나이다. 플로이드의 거북이와 토끼 알고리즘을 이용해서 풀 수 있는데, 이 알고리즘은 마치 이야기 속에서 튀어나온 듯한, 연결 리스트에서 사이클을 찾는 데에 사용되는 기발한 방법이다. 이 알고리즘은 두 주인공, 느린 거북이와 빠른 토끼를 등장시킨다. 이들은 같은 출발점, 즉 리스트의 헤드에서 여정을 시작한다. 이야기는 이렇다: 거북이는 한 번에 한 걸음씩 꾸준히 앞으로 나아간다. 반면, 토끼는 매우 빠르기 때문에, 두 걸음씩 뛴다. 만약 리스트에 사이클이 존재하지 않는다면, 토끼는 리스트의 끝에 도달하여 멈춘다. 하지만..