연결리스트의 가운데에 위치한 값을 찾기

전깃줄 위의 참새. Unsplash 에 Mesh 님이 올림.

들어가는 말

LeetCode의 Reorder List라는 문제를 풀다가 연결리스트의 중앙을 알아내는 재미있는 방법이 있어서 기록합니다.

속도가 다른 두 포인터를 사용하기

연결 리스트의 끝까지 간 다음에 절반을 찾지 말고, 항상 여태까지 온 거리의 절반을 기억하고 있으면 됩니다.

 

let fast = firstNode;
let slow = firstNode;

while (fast !== null && fast.next !== null) {
  fast = fast.next.next;
  slow = slow.next;
}

const mid = slow;

 

물론 이 방법 역시 시간 복잡도 자체는 O(N)으로 끝까지 순회한 다음 처음부터 다시 절반만큼 오는거랑 같습니다. 하지만 반복문을 한 번만 돌기 때문에 실제 실행 시간에는 차이가 있을 것으로 보입니다.