[LeetCode] 234. Palindrome Linked List

 Given the head of a singly linked list, return true if it is a palindrome or false other wise.

---

• 연결리스트를 순회하며 val 값을 리스트에 추가한 후 양 끝에 두 포인터를 잡아 회문인지 체크한다.

# 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:    
        node = head
        val_lst = []

        while node:
            val_lst.append(node.val)
            node = node.next
        
        p1, p2 = 0, len(val_lst) - 1
        while p1 <= p2:
            if val_lst[p1] != val_lst[p2]:
                return False
            p1 += 1
            p2 -= 1
        
        return True

---

Runner 기법

Follow up: Could you do it in O(n) time and O(1) space?

• 공간 복잡도를 상수로 만드려면 위 코드처럼 리스트를 따로 만드는 것이 아닌, 리스트를 순회하면서 바로 회문인지 체크할 수 있어야 한다.

• 이를 위해 런너(Runner) 기법을 사용하는데, 다음과 같은 원리를 가진다.

  • 빠른 런너(Fast Runner), 느린 런너(Slow Runner) 총 두 개의 포인터를 사용한다.
  • 빠른 런너는 두 칸씩 건너뛰고, 느린 런너는 한 칸씩 이동한다. 이 경우 빠른 런너가 연결 리스트의 끝에 도착했을 때, 느린 런너는 중앙에 도착하게 된다.
  • 두 포인터의 위치 차이를 이용하여 병합 지점, 중간 위치, 길이 등을 판별하는 기준으로 사용할 수 있다.

• 회문을 판별하기 위해 slow 가 진행하는 방향과 역순으로 진행하는 연결 리스트 rev 를 구성하여 비교한다.

# 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는 slow의 역순이므로 None부터 시작한다.
        rev = None
        slow = fast = head

        while fast and fast.next:
            fast = fast.next.next
            # slow 포인터를 한 칸씩 전진시키며 현재 slow의 위치를 rev에, 현재 rev의 위치를 rev.next에 연결한다
            # 현재 rev의 위치는 결국 이전 slow의 위치이므로, rev는 slow의 역순으로 연결된다.
            rev, rev.next, slow = slow, rev, slow.next

            # 연결 리스트의 길이가 2n일 경우, fast는 None에서 끝나고, slow는 중앙 바로 다음 노드에 도착한다.
            # 이 경우 따로 조작이 필요없이 바로 회문인지 체크하면 된다.
            # 연결 리스트의 길이가 2n+1일 경우, fast는 마지막 노드에서 끝나고, slow는 정중앙 노드에 도착한다.
            # 이 경우 slow 포인터를 다음 노드로 보내야 rev와 slow의 길이가 같아져 회문을 체크할 수 있다.
        if fast:
            slow = slow.next

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

        # 회문을 만족하여 포인터가 끝까지 이동했다면 rev = None이므로 not rev = True가 된다.
        # 그 외의 경우 rev에 특정 값이 존재하므로 not rev = False가 된다.
        return not rev

• 시간복잡도는 둘 다 $O(n)$이므로 큰 차이가 나지는 않지만, 공간복잡도 면에서 많은 차이가 있는 것을 볼 수 있다.