개념

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

빠른 런너와 느린 런너

위의 그림에서 2개의 포인터는 각각 빠른 런너(Fast Runner), 느린 런너(Slow Runner)라고 부르는데, 대게 빠른 런너(포인터)는 두 칸씩 건너뛰고, 느린 런너(포인터)는 한 칸씩 이동하게 합니다. 이때 빠른 런너가 연결 리스트의 끝에 도달하면, 느린 런너는 정확히 연결 리스트의 중간 지점을 가리키게 됩니다. 이 같은 방식으로 중간 위치를 찾아내면, 여기서부터 값을 비교하거나 뒤집기를 시도하는등 여러모로 활용할 수 있어 연결 리스트 문제에서는 반드시 쓰이는 기법이기도 합니다.

직접 문제를 풀며 자세히 이해해보겠습니다.

예제

풀어볼 예제는 LeetCode - Palindrome Linked List이고 주어진 연결 리스트가 팰린드롬인지의 여부를 판단하는 문제입니다. 여기서 팰린드롬이라는 단어는 거꾸로 뒤집어도 똑같은 단어를 뜻합니다. 예를 들어 "aba", "eye"와 같이 앞뒤로 뒤집고 봐도 똑같은 단어가 팰린드롬입니다.

문제

이 문제를 푸는 방법은 여러가지가 있지만, 여기서는 런너 기법에 대해 알아보기 위해서 런너 기법을 사용해서 문제를 풀이하도록 하겠습니다.

풀이 방법

입력값이 1->2->3->2->1인 연결 리스트에 런너를 적용해 풀이하는 방법을 그림으로 그리면 아래와 같습니다.

1->2->3->3->2->1(짝수) - 예시를 위한 그림(연결 리스트의 총 노드의 갯수가 짝수일 때 fast가 어떻게 움직이는지 확인하기 위해서)

1->2->3->2->1(홀수) - 이 그림에 집중

위 그림에서 파란색으로 표시된 번호 1,2,3,4는 실행 순서를 보여줍니다. 순서에 따라 2개의 런너, 빠른 런너와 느린 런너를 각각 출발시키면, 빠른 런너가 끝에 다다를 때 느린 런너는 정확히 중간 지점에 도달하게 되는 것입니다. 그리고 느린 런너는 중간까지 이동하면서 역순으로 연결 리스트 rev를 만들어 나갑니다. 이제 중간에 도달한 느린 런너가 나머지 경로를 이동할 때, 역순으로 만든 연결 리스트의 값들과 일치하는지 확인해나가면 되는 것입니다.

진행 과정은 아래와 같습니다.

1. 빠른 런너 fast와 느린 런너 slow의 초깃값은 모두 head에서 시작합니다.

slow = fast = head

2. 이제 런너를 이동하는데, 다음과 같이 next가 존재하지 않을 때까지 이동합니다. 그림에서 보았듯이 빠른 런너인 fast는 두 칸씩, 느린 런너인 slow는 한 칸씩 이동합니다.

while fast and fast.next:
    fast = fast.next.next
    ...
    slow = slow.next

3. 그리고 역순으로 연결 리스트 rev를 생성하는 로직을 slow앞에 덧붙입니다.

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

4. 마지막으로 팰린드롬 여부를 확인합니다. 아래와 같이 역순으로 만든 연결 리스트 rev를 반복하면 됩니다.

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

위의 과정을 거치고 정상적으로 비교가 종료됐다면 slow와 rev 모두 끝까지 이동해 None이 될 것입니다. 전체 코드는 아래와 같습니다.

Code

LeetCode 형식

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        # 1단계 과정에 해당
        slow = fast = head
        
        # 런너를 이용해 역순 연결 리스트 구성
        while fast and fast.next:
            fast = fast.next.next
            # 다중 할당 사용
            rev, rev.next, slow = slow, rev, slow.next
        # 노드의 갯수가 홀수라면 가운데 값은 팰린드롬 여부에 필요하지 않기 때문에 slow를 한칸 더 움직인다.
        # fast가 None인지로 홀수를 판별하는 이유는 
        # 총 갯수가 홀수라면 홀수 그림과 같이 fast는 마지막 노드에서 멈춘다.
        # 하지만 총 갯수가 짝수라면 짝수 그림과 같이 fast는 None까지 넘어가서 이를 통해 확인 가능한 것이다.
        if fast:
            slow = slow.next
            
        # 팰린드롬 여부 확인
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        # None인지를 판별
        return not rev

참조
파이썬 알고리즘 인터뷰

틀린 부분은 댓글로 남겨주시면 수정하겠습니다..!!