[Python] 연결리스트 <Runner 기법>

앞서도 몇번 언급했듯이, ArrayList와 같은 연결 리스트는 자료들이 노드로 하나씩 연결되어 있는 형태이기 때문에,  자료의 삽입이나 삭제는 O(1) 의 매우 유리한 시간 복잡도를 가지지만, 탐색은 노드를 따로 불러올 수 없고, 리스트 전체를 훓어가면서 찾아야 하기 때문에 최악의 경우 O(n)의 복잡도를 가진다.

그렇기 때문에 연결 리스트를 탐색, 비교하는 문제를 풀 때, 문제가 조금 복잡해지면 빈번하게 타임 아웃이 일어나기 쉽다.

이번 포스팅에서는 이런 연결 리스트의 탐색 속도를 2개의 포인터를 이용하여 조금이나마 향상시킬 수 있는 방법인 Runner 기법에 대하여 다룰 것이다.

---

1. Runner?

Runner 기법은 연결 리스트를 순회할 때, 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 

2개의 포인터는 각각 Fast Runner, Slow Runner로 불리는데, 대개 빠른 러너는 두 칸씩 메모리를 건너 뛰고, 느린 러너는 한 칸씩 이동한다. 이 때, 빠른 러너가 연결 리스트의 끝에 도달하면, 느린 러너는 정확히 연결 리스트의 중간을 가리키게 된다. 이 경우, 값을 비교하거나 뒤집기를 시도할 수 있는 등 여러모로 사용할 수 있어 연결 리스트를 사용하는 문제에서는 거의 대부분은 사용할 수 있는 기법이다. 

 

2. Runner 기법을 이용한 문제 풀이 <팰린드롬 연결 리스트>

 

정수로 구성되어 있는 연결 리스트가 뒤집어도 똑같은 팰린드롬 구조인지 확인하는 문제이다.

Runner기법을 이용하여, Fast Runner가 연결 리스트의 마지막 노드에 도달할 때까지, Slow Runner는 연결 리스트를 하나 하나 지나쳐가며 역순의 연결 리스트를 만들어 놓은 뒤, 중간 지점에서 비교하면 쉽게 풀 수 있는 문제이다.

연결리스트또한 다음과 같이 간단하게 구현할 수 있다.

class ListNode:
    def __init__(self, data):
        self.val = data
        self.next = None


def isPel(head: ListNode) -> bool:
    rev = None
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next

    if fast:
        slow = slow.next

    while rev and rev.val == slow.val:
        slow, rev = slow.next, rev.next

    return not rev


if __name__ == '__main__':
    linked = [1, 2, 2, 1]
    head = ListNode(linked[0])
    tail = head
    e = 1

    while e < len(linked):
        tail.next = ListNode(linked[e])
        tail = tail.next
        e += 1

    print(isPel(head))