파이썬으로 연결 리스트의 뒤에서 K번째 노드 찾기 — 단 한 번의 순회로 해결하기

단일 연결 리스트(singly linked list)가 하나 주어졌다고 가정해 보겠습니다. 이때 뒤에서 k번째(0 인덱스 기준)에 있는 노드의 값을 찾아야 하며, 이 문제는 단 한 번의 순회(single pass)만으로 해결해야 합니다.

예를 들어 입력이 node = [5, 4, 6, 3, 4, 7]이고 k = 2라면, 출력은 3이 됩니다. 뒤에서 두 번째 노드는 전체 리스트에서 인덱스 3에 해당하며, 그 노드의 값이 3이기 때문입니다.

해결 접근 방법: 두 포인터(Two-Pointer) 기법

리스트 길이를 먼저 계산한 뒤 다시 순회하는 대신, 간격이 k만큼 벌어진 두 개의 포인터를 활용하면 한 번의 순회로 문제를 해결할 수 있습니다. 알고리즘의 동작 단계는 다음과 같습니다.

1. klast와 last 두 포인터를 모두 헤드(head) 노드로 초기화합니다.

2. last 포인터를 정확히 k칸 앞으로 이동시켜, 두 포인터 사이의 간격을 k로 만듭니다.

3. last가 마지막 노드에 도달할 때까지 두 포인터를 함께 한 칸씩 이동시킵니다.

4. 반복이 종료되면 klast가 가리키는 노드가 바로 뒤에서 k번째 노드이므로, 해당 노드의 값을 반환합니다.

두 포인터 사이의 거리를 k로 유지한 채 함께 움직이기 때문에, last가 리스트의 끝에 닿는 순간 klast는 자연스럽게 뒤에서 k번째 위치에 도달하게 됩니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

다음 파이썬 구현을 통해 더 쉽게 이해할 수 있습니다.

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, k):
        klast = node
        last = node
        # last 포인터를 k칸 먼저 이동
        for i in range(k):
            last = last.next
        # last가 끝에 도달할 때까지 두 포인터를 함께 이동
        while last.next:
            last = last.next
            klast = klast.next
        return klast.val

ob = Solution()
l1 = make_list([5, 4, 6, 3, 4, 7])
print(ob.solve(l1, 2))

입력

[5, 4, 6, 3, 4, 7], 2

출력

3