[알고리즘] 런너(Runner) 기법 (링크드 리스트 문제 풀기)

런너(Runner) 기법이란?

런너(Runner) 기법은 링크드 리스트를 검색할 때 속도가 다른 2개의 포인터를 사용하는 기법입니다. 예를 들어 한 포인터가 한 칸을 이동할 때 다른 포인터는 두 칸을 이동하는 방법이 있습니다. 이 기법을 이용하면 링크드 리스트의 중간 위치나 특정 조건의 길이를 판단할 때 유용하개 사용 할 수 있습니다.

링크드 리스트의 가운데 노드

> 포인터를 런너(Runner)라고 설명하겠습니다.

한 칸씩 이동하는 느린 런너(Slow Runner)와 두 칸씩 이동하는 빠른 런너(Fast Runner)가 있다고 가정하겠습니다.

끝을 알 수 없는 어느 링크드 리스트에서 위 방법을 빠른 런너(Fast Runner)가 리스트의 끝까지 도달했다면 느린 런너(Slow Runner)는 링크드 리스트의 중간 지점을 가리키고 있을 것입니다.

이런 방법으로 리스트의 중간 노드를 찾는다면 그 지점부터 비교를 시도하는 등 다양한 방법으로 활용할 수 있습니다. 또한 이런 이유 때문에 링크드 리스트 문제에서 많이 사용되는 기법입니다.

관련 문제

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/