Middle of the Linked List — slow/fast 포인터로 중간 노드 찾기

연결 리스트의 중간 노드 찾기, 어떤 문제인가요?

LeetCode 876번 문제는 이렇게 주어집니다.

단일 연결 리스트의 head가 주어졌을 때, 연결 리스트의 중간 노드를 반환합니다. 중간 노드가 두 개라면 두 번째 중간 노드를 반환합니다.

예시는 이렇습니다.

• head = [1, 2, 3, 4, 5] → [3, 4, 5]
• head = [1, 2, 3, 4, 5, 6] → [4, 5, 6]

여기서 출력이 [3, 4, 5]처럼 보이는 이유는 값 3 하나를 반환하는 것이 아니라, 값이 3인 노드 자체를 반환하기 때문입니다. 그 노드부터 끝까지 이어진 리스트가 출력됩니다.

제약은 다음과 같습니다.

• 리스트의 노드 수는 [1, 100] 범위
• 1 <= Node.val <= 100

핵심은 연결 리스트에서는 배열처럼 list[n / 2]로 바로 접근할 수 없다는 점입니다. 이 글에서는 노드를 배열에 모아 인덱스로 찾는 풀이부터, 길이를 먼저 세는 두 번 순회 풀이, 그리고 slow/fast 포인터로 한 번에 찾는 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

LeetCode의 ListNode 형태

Kotlin 기준으로 LeetCode의 연결 리스트 노드는 대략 이런 형태입니다.

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

val은 Kotlin 키워드이므로 백틱으로 감싸서 `val`처럼 접근합니다. 이 문제에서는 노드 값을 바꾸지 않고, next 포인터를 따라가며 중간 노드를 찾기만 하면 됩니다.

Phase 1. 노드를 배열에 모은 뒤 인덱스로 찾기

가장 직관적인 방법은 연결 리스트를 처음부터 끝까지 순회하면서 노드를 배열에 담는 것입니다.

fun middleNode(head: ListNode?): ListNode? {
    val nodes = mutableListOf<ListNode>()
    var current = head

    while (current != null) {
        nodes.add(current)
        current = current.next
    }

    return nodes[nodes.size / 2]
}

head = [1, 2, 3, 4, 5]라면 nodes는 이렇게 됩니다.

index:  0  1  2  3  4
node:   1  2  3  4  5

노드 수는 5이고, 5 / 2 = 2이므로 nodes[2], 즉 값이 3인 노드를 반환합니다.

짝수 길이인 [1, 2, 3, 4, 5, 6]도 봅시다.

index:  0  1  2  3  4  5
node:   1  2  3  4  5  6

노드 수는 6이고, 6 / 2 = 3이므로 nodes[3], 즉 값이 4인 노드를 반환합니다. 문제에서 요구하는 두 번째 중간 노드와 정확히 맞습니다.

시간 복잡도는 O(n)입니다. 모든 노드를 한 번 방문합니다. 공간 복잡도는 노드를 배열에 저장하므로 O(n)입니다.

Phase 2. 길이를 먼저 세고, 절반만큼 다시 이동하기

배열에 모든 노드를 저장하지 않아도 됩니다. 먼저 리스트 길이를 세고, 다시 head부터 length / 2번 이동하면 중간 노드에 도착합니다.

fun middleNode(head: ListNode?): ListNode? {
    var length = 0
    var current = head

    while (current != null) {
        length++
        current = current.next
    }

    current = head
    repeat(length / 2) {
        current = current?.next
    }

    return current
}

[1, 2, 3, 4, 5, 6]에서는:

• 첫 번째 순회에서 length = 6
• length / 2 = 3
• head에서 3번 이동: 1 -> 2 -> 3 -> 4
• 값이 4인 노드 반환

이 풀이도 두 번째 중간 노드를 자연스럽게 반환합니다. 정수 나눗셈에서:

• 길이 5 → 5 / 2 = 2번 이동 → 세 번째 노드
• 길이 6 → 6 / 2 = 3번 이동 → 네 번째 노드

시간 복잡도는 O(n)입니다. 다만 리스트를 두 번 순회합니다. 빅오로는 O(n)이지만, 실제 방문 횟수는 Phase 1이나 Phase 3보다 많습니다. 공간 복잡도는 O(1)입니다.

Phase 3. slow/fast 포인터로 한 번에 찾기

가장 좋은 풀이는 포인터 두 개를 쓰는 방식입니다.

• slow: 한 번에 한 칸 이동
• fast: 한 번에 두 칸 이동

fast가 리스트 끝에 도착하면, slow는 정확히 중간에 도착합니다.

fun middleNode(head: ListNode?): ListNode? {
    var slow = head
    var fast = head

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

    return slow
}

홀수 길이 예시 [1, 2, 3, 4, 5]를 따라가 봅시다.

초기: slow = 1, fast = 1

1회 이동: slow = 2, fast = 3
2회 이동: slow = 3, fast = 5

이제 fast.next == null이므로 멈춥니다. slow는 값이 3인 노드입니다.

짝수 길이 예시 [1, 2, 3, 4, 5, 6]도 보겠습니다.

초기: slow = 1, fast = 1

1회 이동: slow = 2, fast = 3
2회 이동: slow = 3, fast = 5
3회 이동: slow = 4, fast = null

반복문이 끝나면 slow는 값이 4인 노드입니다. 즉 두 번째 중간 노드를 반환합니다.

시간 복잡도는 O(n)입니다. fast가 두 칸씩 움직이므로 반복 횟수는 대략 n / 2번입니다. 추가 공간은 포인터 두 개뿐이므로 O(1)입니다.

왜 slow/fast 포인터가 중간을 가리키나요?

반복문이 한 번 실행될 때마다 두 포인터는 이렇게 움직입니다.

slow: 1칸
fast: 2칸

즉 fast는 항상 slow보다 두 배 빠르게 이동합니다. 그래서 fast가 리스트 끝까지 갔을 때, slow는 그 절반 거리만 이동한 상태가 됩니다. 그 위치가 중간 노드입니다.

이 문제의 반복 조건은 다음입니다.

while (fast?.next != null)

이 조건 덕분에 짝수 길이에서는 slow가 한 번 더 이동해 두 번째 중간 노드에 도착합니다.

예를 들어 길이 6에서 반복은 3번 실행됩니다.

slow 이동 횟수 = 3
도착 위치 = index 3 = 네 번째 노드

0-index 기준 n / 2 위치가 두 번째 중간 노드이므로, 문제 요구사항과 맞습니다.

참고: 이 문제의 투 포인터는 Container With Most Water처럼 양끝에서 좁혀 가는 방식이 아닙니다. 같은 투 포인터라도 여기서는 한 포인터가 다른 포인터보다 빠르게 움직이는 속도 차이 패턴입니다.

반환값은 값이 아니라 노드입니다

이 문제에서 헷갈리기 쉬운 부분은 반환 타입입니다. 정답으로 3이나 4라는 값을 반환하는 것이 아니라, 해당 값을 가진 ListNode를 반환해야 합니다.

예를 들어 입력이:

1 -> 2 -> 3 -> 4 -> 5

이면 값 3을 반환하는 것이 아니라:

3 -> 4 -> 5

로 이어지는 노드 참조를 반환합니다. 그래서 LeetCode 출력도 [3, 4, 5]처럼 보입니다.

Kotlin 함수 시그니처도 이를 드러냅니다.

fun middleNode(head: ListNode?): ListNode?

반환 타입이 Int가 아니라 ListNode?입니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	반환 노드부터의 리스트	이유
[1]	[1]	노드가 하나면 그 노드가 중간
[1, 2]	[2]	중간 두 개 중 두 번째 노드
[1, 2, 3]	[2, 3]	홀수 길이의 정확한 가운데
[1, 2, 3, 4]	[3, 4]	짝수 길이의 두 번째 중간
[1, 2, 3, 4, 5]	[3, 4, 5]	예시 1
[1, 2, 3, 4, 5, 6]	[4, 5, 6]	예시 2

입력 리스트의 노드 수는 최소 1개입니다. 따라서 head가 실제로는 null로 들어오지 않는다고 봐도 되지만, LeetCode의 Kotlin 시그니처가 nullable을 쓰므로 코드도 ListNode?를 안전하게 처리하도록 작성했습니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
노드를 배열에 저장	O(n)	O(n)	인덱스로 바로 찾을 수 있어 가장 직관적
길이 세기 + 다시 이동	O(n)	O(1)	공간은 줄지만 리스트를 두 번 순회
slow/fast 포인터	O(n)	O(1)	한 번의 순회로 두 번째 중간 노드까지 처리

마무리

1. 연결 리스트는 배열처럼 중간 인덱스로 바로 접근할 수 없습니다 — next를 따라 순차적으로 이동해야 합니다
2. 중간 노드가 두 개면 두 번째 중간 노드를 반환해야 합니다 — 짝수 길이에서 n / 2번 이동한 위치입니다
3. slow/fast 포인터는 속도 차이를 이용해 중간을 찾습니다 — fast가 두 칸 갈 때 slow는 한 칸만 갑니다
4. while (fast?.next != null) 조건은 짝수 길이에서 두 번째 중간 노드를 반환하게 만듭니다 — [1,2,3,4,5,6]에서 4가 반환됩니다
5. 반환값은 노드 값이 아니라 노드 참조입니다 — 그래서 출력이 중간 노드부터 끝까지의 리스트로 표시됩니다