Palindrome Linked List (Linked List)

LeetCode의 Palindrome Linked List 문제다.

Palindrome Linked List - LeetCode

회문(Palindrome)을 구하는 문제인데 이번에는 단방향 연결 리스트를 활용하고 있다. 가장 먼저 생각해볼 수 있는 방법은 연결 리스트를 리스트로 바꿔서 거꾸로 뒤집어서 비교해보는 것이다.

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        current = head
        nodeList = []
        
        while current is not None:
            nodeList.append(current.val)
            current = current.next
        
        return nodeList == nodeList[::-1]

슬라이싱을 이용하면 reverse 메서드를 이용하지 않아도 쉽게 뒤집을 수 있다. 그러나 책에서는 다른 방법으로 런너(Runner)를 이용한 풀이를 제공하고 있는데 이는 처음 보는 방법이기 때문에 이곳에 적어보도록 하겠다.

이 런너란 단순히 연결 리스트를 훑는 포인터를 의미한다. 이 런너는 두 개를 유지하는데 한 번에 하나씩 이동하는 느린 런너(Slow Runner), 두 개씩 이동하는 빠른 런너(Fast Runner)를 유지한다. 위의 그림에서는 위의 화살표가 느린 런너, 아래의 화살표가 빠른 런너가 될 것이다. 그럼 이걸로 어떻게 연결 리스트의 회문 여부를 파악할 수 있다는 것일까? 이는 느린 런너가 한 번에 하나씩 노드를 탐색하고 빠른 런너는 두 개씩 탐색한다는 점을 생각해볼 수 있다.

위의 그림처럼 빠른 런너는 느린 런너의 두 배만큼 움직인다. 빠른 런너는 node.next.next처럼 두 개씩 탐색하기 때문에 현재 노드와 현재 노드가 가리키는 다음 노드가 둘 다 null이 아니어야 에러가 발생하지 않는다는 것을 명심하자. 그런데 빠른 런너가 모든 노드를 다 탐색했을 때 느린 런너를 보면 항상 연결 리스트의 중간을 가리키고 있는 것을 볼 수 있다. 짝수 개의 노드가 있는 리스트에서는 정중앙이 없기 때문에 가운데 두 개의 노드 중에서 오른쪽 노드를 가리키고 있으며 홀수 개의 노드가 있는 리스트에서는 정중앙의 노드를 가리키고 있다.

이를 이용한다면 빠른 런너가 연결 리스트를 탐색하는 동안 느린 런너가 탐색하는 노드들을 저장해 뒀다가 빠른 런너의 탐색이 끝난다면, 즉 느린 런너가 연결 리스트의 정중앙에 도달했다면 거기서부터 하나씩 탐색하면서 저장된 노드들을 비교하는 방법이다. 그러나 홀수 개의 노드가 있을 경우 정중앙의 노드는 제외하고 회문을 판단해야 하기 때문에 느린 런너가 노드를 한번 더 탐색해야 한다.

 

이를 기반으로 작성한 코드는 다음과 같다.

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        reverseListNodes = [head]
        runnerSlow, runnerFast = head, head
        
        # 빠른 런너가 2개씩 건너뛰며 노드를 탐색하는 동안...
        while runnerFast and runnerFast.next:
        	# 느린 런너가 탐색하는 노드를 리스트에 저장
            reverseListNodes.append(runnerSlow.val)
            # 느린 런너, 빠른 런너 이동
            runnerSlow = runnerSlow.next
            runnerFast = runnerFast.next.next
        
        # 홀수 개의 노드가 있을 경우 중앙을 제외한 오른쪽 절반부터 탐색하도록 느린 런너 이동
        if runnerFast:
            runnerSlow = runnerSlow.next
            
        # 느린 런너가 탐색하며 저장했던 왼쪽 절반 노드들과 이제 느린 런너가 탐색할 오른쪽 노드 비교
        while reverseListNodes and runnerSlow:
            if reverseListNodes.pop() == runnerSlow.val:
                runnerSlow = runnerSlow.next
            else:
                return False
            
        return True

위의 그림에서도 볼 수 있지만 연결 리스트에 노드가 홀수 개, 예를 들어 5개가 있을 경우 빠른 런너는 노드 1에서 노드 3, 노드 5로 두 번 이동한다. 그리고 노드 5의 다음 노드는 존재하지 않기 때문에 빠른 런너는 더 이상 움직이지 않는다. 느린 런너도 두 번 이동하면 노드 1에서 노드 2, 노드 3으로 연결 리스트의 정중앙까지 이동한다.

 

그러나 회문을 비교하려면 정중앙 노드를 제외한 양쪽 절반을 비교해야 하기 때문에 노드 4와 노드 5를 아까 탐색한 노드 1, 노드 2와 비교해야 한다. 그래서 노드 3을 가리키고 있는 느린 런너를 한번 더 옮겨줘야 노드 1, 노드 2와 노드 4, 노드 5를 비교하여 회문 여부를 판단할 수 있는 것이다.

 

한번 더 옮기는 것을 판단하는 것은 현재 빠른 런너가 가리키는 노드가 null인지 아닌지로 판단할 수 있다. 맨 처음 노드부터 시작해서 2개씩 이동하는 만큼 연결 리스트에 짝수 개의 노드가 있다면 빠른 런너는 null을 가리키게 되고 홀수 개의 노드가 있다면 마지막 노드를 가리키기 때문이다.

 

그러면 짝수 개, 예를 들어 6개가 있을 경우 어떻게 될까? 빠른 런너는 노드 1부터 노드 3, 노드 5, 노드 7로 3번 이동한다. 노드 5에서는 노드 5 자체와 노드 5가 가리키는 다음 노드 6은 null이 아니기 때문에 빠른 런너는 두 번 이동해서 노드 7까지 이동하고 null이 돼서 더 이상 움직이지 않는 것이다.

 

이제 느린 런너도 노드 1부터 3번 이동하면 노드 2, 노드 3, 노드 4가 된다. 그럼 지금까지 탐색한 노드 1, 노드 2, 노드 3과 지금부터 탐색할 노드 4, 노드 5, 노드 6을 가지고 회문을 비교하면 된다. 이는 6개의 노드를 딱 절반으로 나눈 것과 동일하다.