단일 연결 리스트(singly linked list)의 헤드 노드가 주어졌을 때, 리스트의 중간 노드 값을 찾는 것이 이번 문제의 목표입니다. 리스트의 길이가 짝수여서 중간에 해당하는 노드가 두 개라면, 그중 두 번째 중간 노드의 값을 반환해야 합니다. 또한 전체 리스트를 딱 한 번만 순회(single pass)하는 조건 안에서 해결해야 한다는 점이 핵심 제약입니다.
예를 들어 입력이 [5,9,6,4,8,2,1,4,5,2]라면 출력은 2가 됩니다. 리스트 길이가 10으로 짝수이므로 다섯 번째 요소(8)와 여섯 번째 요소(2)가 모두 중간에 해당하지만, 규칙에 따라 두 번째 중간 노드인 2를 반환하는 것입니다.
문제 해결 접근 방식
이 문제는 두 개의 포인터를 활용하는 two-pointer 기법으로 깔끔하게 해결할 수 있습니다. 빠른 포인터(node)는 매 반복마다 한 칸씩 앞으로 이동하는 반면, 느린 포인터(p)는 카운터 d를 이용해 두 칸 전진할 때마다 한 칸씩만 이동합니다. 이렇게 하면 리스트의 총 길이를 미리 알지 못하더라도, 순회가 끝나는 시점에 느린 포인터가 자연스럽게 중간 지점에 도달하게 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- p := node — 느린 포인터를 헤드 노드로 초기화합니다.
- d := 0, l := 0 — 카운터 변수를 초기화합니다.
- node가 null이 아닌 동안 아래 과정을 반복합니다.
- d가 2가 아니면: node를 다음 노드로 이동하고, l과 d를 각각 1씩 증가시킵니다.
- d가 2이면: p를 다음 노드로 이동하고, d를 0으로 되돌립니다. - 반복이 종료되면, l이 홀수일 때는 p의 값을, 짝수일 때는 p의 다음 노드 값을 반환합니다.
전체 흐름을 더 잘 이해할 수 있도록 아래 구현 예제를 살펴보겠습니다.
예제 코드
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
class Solution:
def solve(self, node):
p = node
d = 0
l = 0
while node:
if d != 2:
node = node.next
l += 1
d += 1
else:
p = p.next
d = 0
return p.val if l & 1 else p.next.val
ob = Solution()
head = make_list([5,9,6,4,8,2,1,4,5,2])
print(ob.solve(head))
입력
[5,9,6,4,8,2,1,4,5,2]
출력
2
시간 및 공간 복잡도
이 알고리즘은 리스트를 정확히 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 자료구조를 사용하지 않기 때문에 공간 복잡도 역시 O(1)입니다. 리스트 길이를 먼저 계산한 뒤 다시 처음부터 순회하는 방식과 달리, 단일 패스 조건을 그대로 지키면서 중간 노드를 찾을 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.