[알고리즘] 팰린드롬 연결 리스트

팰린드롬 연결 리스트

내 풀이

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

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

속도가 매우 느리게 나왔다.

책 풀이 1

    def isPalindrome(self, head: ListNode) -> bool:
        q: List = []
        
        if not head:
            return True
        
        node = head
        # 리스트 변환
        while node is not None:
            q.append(node.val)
            node = node.next
        
        # 팰린드롬 판별
        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False
        return True

내 풀이와 마찬가지로 리스트를 이용하지만 초기 조건을 주었고, 또한 비교할 때 앞뒤로 하나씩 빼며 비교하였다.

책 풀이 2

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        q: Deque = []

        if not head:
            return True

        node = head
        # 리스트 변환
        while node is not None:
            q.append(node.val)
            node = node.next

        # 팰린드롬 판별
        while len(q) > 1:
            if q.popleft() != q.pop():
                return False
        return True

책 풀이 1에서 앞뒤로 뺀다는 점에 착안하여 덱을 쓰면 더욱 효율적이다.

책 풀이 3

    def isPalindrome(self, 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

런너(Runner) 기법을 활용한 것이다. slow 런너와 faster 런너를 동시에 출발시키면 fast가 끝에 도착할 때 slow는 정확히 중간 지점에 도착한다. 느린 런너는 중간까지 가면서 역순으로 연결 리스트 rev를 만든다. 중간 지점에서 느린 런너가 끝까지 도착할 때, 역순으로 만든 연결 리스트와 일치하는지 확인하면 된다.