[LeetCode] 234. 팰린드롬 연결 리스트(Palindrome Linked List)

연결 리스트가 팰린드롬 구조인지 판별하라

팰린드롬 : 이름을 거꾸로 뒤집어도 처음과 같은 문자.

ex. 기러기, 미레미, anna

 

 

 

 

 

 

1. 내가 직접 푼 코드

 

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

 

해설:

 

리스트 하나를 생성하고

연결 리스트의 값들을 일일히 리스트에 추가했다.

이렇게 하는 이유는 문제 특성상 앞과 뒤를 비교해야 하는데

연결 리스트는 원하는 위치를 자유롭게 추출하는 게 쉽지 않다.

따라서 일단 리스트에 값들을 추가한 뒤, 슬라이싱을 이용해 값이 같은지 비교하도록 했다.

 

 

RunTime : 884ms

 

 

 

 

 

 

 

** 깔끔한 답안 **

 

 

2. 리스트 변환

 

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        q = []
 
        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

 

해설:

 

내가 푼 방법과 유사하다.

리스트로 받는 것은 거의 똑같고

다만, 리스트에 내장된 기능인 pop을 이용하여

팰린드롬을 판별하고자 하였다.

하지만 런타임이 큰걸로 봐선 내가 사용한 슬라이싱보다 시간을 많이 잡아먹는 것 같다.

 

 

RunTime : 1340ms

 

 

 

 

 

 

3. 데크를 이용한 최적화

 

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        q = collections.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

 

해설:

 

앞과 뒤의 요소를 비교한다는 점에서

리스트보다는 데크를 이용하는 것이 더 효율적이다.

왜냐하면 리스트로 첫번째 값을 꺼내오면 모든 값을 한 칸씩 시프팅 해야 되는데

이때 시간 복잡도 O(n)이 발생하기 때문이다.

따라서 데크를 사용할 경우 이중 연결 리스트 구조라서

양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)에 실행된다.

 

 

RunTime : 812ms

 

 

 

 

 

 

4. 런너를 이용한 풀이

 

class Solution:
    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
        # 연결 리스트가 짝수냐 홀수냐에 따라 slow를 한 번 더 진행시켜줘야함
        if fast:
            slow = slow.next
 
        # 팰린드롬 여부 확인
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev

 

해설:

 

연결 리스트를 다른 자료형으로 변환하지 않고

있는 그대로 풀이하는 방법이다.

빠른 러너와 느린 러너를 각각 출발시킨다.

빠른 러너는 2칸씩, 느린 러너는 한 칸씩 이동하는데

이렇게 되면 빠른 러너가 목적지에 도착했을 때 느린 러너는 중간 지점에 도달하게 된다.

느린 러너가 중간 지점에 도달하는 동안 rev을 통해 역순으로 연결 리스트를 생성하게 되는데

이제부터 rev을 통해 만든 역순 연결 리스트와

slow가 나아갈 연결 리스트를 비교하면 팰린드롬 여부를 판별할 수 있다.

 

 

RunTime : 644ms

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]