Linked List의 Two Pointer 복습하기

Linked List에서 뒤에서 k번째 노드를 찾을 때, 길이를 먼저 구하는 방식과 slow/fast 포인터 방식이 어떤 차이가 있는지 그리고 방법을 까먹지 않기 위한 회고록입니다.

개요

Linked List 문제를 풀다가 뒤에서 k번째 노드를 찾는 문제를 만났습니다.처음에는 전체 길이를 먼저 구한 다음, 앞에서 몇 번째 노드인지 계산해서 다시 찾는 방식으로 풀었습니다.

사실 예전에 slow, fast 포인터로 푸는 방식을 본 적이 있었습니다. 그런데 시간이 꽤 지나고 다시 보니까 방법이 바로 떠오르지 않았습니다.역시 알고리즘 문제는 한 번 이해했다고 끝나는 게 아니라, 꾸준히 다시 보고 풀어보는 게 답이라는 생각이 들었습니다.

제가 처음 푼 방식

제가 먼저 생각한 방식은 Linked List의 길이를 먼저 구하는 것이었습니다.

def get_kth_node_from_last(self, k):
    if k <= 0:
        return False

    index = self.get_array_len() - k
    return self.find_node(index)

흐름은 단순합니다.

1. Linked List 전체 길이를 구합니다.
2. 뒤에서 k번째 노드는 앞에서 전체 길이 - k번째 노드라는 점을 이용합니다.
3. 다시 head부터 해당 index까지 이동합니다.

예를 들어 노드가 6 -> 7 -> 8이고 k = 2라면, 전체 길이는 3입니다. 뒤에서 2번째 노드는 앞에서 3 - 2 = 1번 index에 있는 노드라서 값은 7이 됩니다.

이 방식은 제가 보기에는 가장 직관적이었습니다. 뒤에서 몇 번째인지 바로 감이 안 오면, 전체 길이를 구해서 앞에서 몇 번째인지로 바꿔 생각하면 되기 때문입니다.

Two Point slow/fast 방식

def get_kth_node_from_last_slow_fast(self, k):
    slow = self.head
    fast = self.head

    for i in range(k):
        fast = fast.next

    while fast is not None:
        slow = slow.next
        fast = fast.next

    return slow

이 방식은 처음에 fast를 k칸 먼저 보냅니다. 그러면 slow와 fast 사이에는 k칸 차이가 생깁니다. 그 상태에서 둘을 같이 한 칸씩 움직이면, fast가 끝에 도착했을 때 slow는 자연스럽게 뒤에서 k번째 노드에 있게 됩니다.

처음 방법 보다 덜 직관적이지만 핵심은 두 포인터 사이의 간격을 k로 유지한다는 점이었습니다. 뒤에서 k번째를 직접 세는 대신, 앞서 간 포인터가 끝에 닿는 순간을 이용하는 방식입니다.

시간복잡도 차이

시간복잡도만 보면 두 방식 모두 O(n)입니다. 제가 푼 방식은 길이를 구할 때 한 번 순회하고, 다시 원하는 index까지 한 번 더 이동합니다. 그래서 최악의 경우 거의 2n에 가깝게 움직일 수 있습니다.

slow/fast 방식은 fast를 먼저 k칸 보낸 다음, slow와 fast를 같이 움직입니다. 결국 전체적으로 봤을 때도 노드를 한 방향으로 훑는 구조라 O(n)입니다.

빅오 표기에서는 O(2n)도 결국 O(n)으로 보기 때문에 둘의 시간복잡도는 같습니다. 다만 실제 이동 횟수나 문제에서 요구하는 조건은 조금 다르게 볼 수 있습니다.

그러면 언제 어떤 방식을 쓰는 게 좋을까

저는 단순히 정답을 빠르게 떠올리는 상황이라면 길이를 먼저 구하는 방식도 충분히 괜찮다고 생각했습니다. 전체 길이를 구하고, 앞에서 몇 번째인지 계산하는 흐름이 눈에 잘 보이기 때문입니다.

특히 Linked List에 익숙하지 않을 때는 이 방식이 더 안정적으로 느껴집니다.내가 지금 무엇을 구하고 있는지 단계가 명확해서 실수도 덜할 것 같습니다.

반대로 slow/fast 방식은 Linked List 문제에서 자주 나오는 패턴을 익히기 좋았습니다.전체 길이를 따로 저장하지 않고, 포인터 사이의 간격만 이용해서 답을 찾는 방식이기 때문입니다.

문제에서 **"한 번의 순회로 풀어라"**라고 하거나, 전체 길이를 미리 알 수 없는 상황처럼 생각해야 한다면 slow/fast 방식이 더 자연스럽습니다. 코딩테스트에서도 이런 의도를 가진 문제라면 예제 풀이처럼 two pointer 방식이 더 기대되는 풀이일 수 있습니다.

주의할 점

예제 코드에서는 k가 Linked List 길이보다 큰 경우를 따로 처리하지 않았습니다. 이 경우 for i in range(k)를 돌다가 fast가 None이 된 상태에서 다시 fast.next를 접근할 수 있어서 에러가 날 수 있습니다.

조금 더 안전하게 쓰려면 이런 조건을 같이 확인하는 게 좋습니다.

def get_kth_node_from_last_slow_fast(self, k):
    if k <= 0:
        return False

    slow = self.head
    fast = self.head

    for i in range(k):
        if fast is None:
            return False
        fast = fast.next

    while fast is not None:
        slow = slow.next
        fast = fast.next

    return slow

핵심 포인트

• 두 방식 모두 시간복잡도는 O(n)입니다.
• 제가 푼 방식은 전체 길이를 먼저 구해서 앞에서 몇 번째인지 계산하는 방식입니다.
• slow/fast 방식은 두 포인터 사이의 간격을 k로 유지해서 뒤에서 k번째 노드를 찾는 방식입니다.
• 시간복잡도가 같다면, 단순하고 직관적인 풀이가 필요할 때는 길이를 먼저 구하는 방식도 괜찮습니다.
• Linked List의 two pointer 패턴을 익히거나, 한 번의 순회가 요구되는 문제라면 slow/fast 방식을 선택하는 게 더 좋습니다.

개인적으로는 이렇게 정리했습니다.

처음 이해할 때는 길이를 먼저 구하는 방식이 편하고, Linked List 문제 풀이 패턴으로는 slow/fast 방식을 익혀두는 게 좋다고 생각했습니다.