문제 소개
이번 글에서는 JavaScript를 이용해 연결 리스트(Linked List)의 중간 노드를 찾는 방법을 알아보겠습니다.
함수는 연결 리스트의 head(첫 번째 노드)를 유일한 인자로 받으며, 리스트의 가장 중앙에 위치한 노드에 저장된 값을 반환해야 합니다. 만약 중앙에 해당하는 노드가 두 개라면, 그중 두 번째 노드의 값을 반환하는 것이 규칙입니다.
예시
다음과 같은 연결 리스트가 주어졌다고 가정해 봅시다.
입력:
[4, 6, 8, 9, 1]
출력:
const output = 8;
리스트의 길이가 5이므로 정확히 중앙에 있는 값은 8입니다. 따라서 결과로 8을 반환하면 됩니다.
해결 접근 방식: 느린 포인터와 빠른 포인터
이 문제를 푸는 가장 우아한 방법은 투 포인터(Two Pointer) 기법, 즉 '느린 포인터(slow)'와 '빠른 포인터(fast)'를 함께 사용하는 것입니다.
- slow 포인터: 한 번에 한 칸씩 앞으로 이동합니다.
- fast 포인터: 한 번에 두 칸씩 앞으로 이동합니다.
fast 포인터가 리스트의 끝에 도달하는 순간, slow 포인터는 자연스럽게 리스트의 정중앙에 위치하게 됩니다. 이 방법은 리스트의 전체 길이를 미리 계산할 필요가 없어 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적입니다.
전체 코드 예제
먼저 Node와 LinkedList 클래스를 정의하고, 이어서 중간 노드를 찾는 함수를 구현합니다.
class Node {
constructor(data) {
this.data = data;
this.next = null;
};
};
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
};
};
LinkedList.prototype.add = function(data) {
const newNode = new Node(data);
let curr;
if(this.head === null) {
this.head = newNode;
} else {
curr = this.head;
while(curr.next) {
curr = curr.next;
}
curr.next = newNode;
};
this.size++;
};
const list = new LinkedList();
list.add(4);
list.add(6);
list.add(8);
list.add(9);
list.add(1);
const findMiddle = (head) => {
let slow = head;
let fast = head;
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow.data;
};
console.log(findMiddle(list.head));실행 결과
8
코드 동작 원리 상세 분석
위 코드가 어떻게 동작하는지 단계별로 살펴보겠습니다.
- 초기화: slow와 fast 포인터 모두 head에서 시작합니다.
- 반복 조건: fast가 null이 아니고, fast.next도 존재하는 동안 반복합니다. 이 조건은 홀수 길이와 짝수 길이 리스트 모두를 안전하게 처리합니다.
- 포인터 이동: 반복할 때마다 slow는 한 칸, fast는 두 칸씩 이동합니다.
- 종료 시점: fast가 마지막 노드 또는 null에 도달하면 반복이 종료되고, slow는 정확히 중간(짝수 길이일 경우 두 중간 노드 중 두 번째)에 위치합니다.
예를 들어 [4, 6, 8, 9, 1] 리스트에서는 다음과 같이 진행됩니다.
- 1회전 후: slow → 6, fast → 9
- 2회전 후: slow → 8, fast → null (반복 종료)
- 결과: slow.data인 8 반환
마무리
투 포인터 기법은 연결 리스트 문제에서 중간 노드 찾기뿐만 아니라 사이클 감지, k번째 노드 찾기 등 다양한 상황에서 활용되는 핵심 패턴입니다. 리스트를 한 번만 순회하면서도 추가 메모리 없이 답을 구할 수 있다는 점에서 면접에서도 자주 등장하는 필수 개념이니 꼭 익혀두시길 바랍니다.