LeetCode 234. Palindrome Linked List

팰린드롬의 LinkedList 버전이다.

팰린드롬이 맞다면 True, 아니라면 False를 반환한다.

풀이

나의 풀이

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head:
            return True

        list = []
        sample = head
        while sample:
            list.append(sample.val)
            sample = sample.next

        while len(list) > 1:
            if list.pop(0) != list.pop():
                return False

        return True

배열을 사용해서 풀이하였다.

LinkedList의 값들을 배열에 순서대로 하나씩 값을 삽입한 다음, 이전 팰린드롬 문제 풀이와 비슷한 방식으로 첫 번째 원소와 마지막 원소를 꺼내 비교하고 같지 않는 순간이 있다면 그 즉시 False를 반환, 그렇지 않다면 True를 반환한다.

결과값1

---

Deque 풀이

class Solution:
    def isPalindrome2(self, head: Optional[ListNode]) -> bool:
        if not head:
            return True

        deque = collections.deque()
        sample = head
        while sample:
            deque.append(sample.val)
            sample = sample.next

        while len(deque) > 1:
            if deque.popleft() != deque.pop():
                return False

        return True

배열대신 데크를 사용하는 것이다.

데크는 popleft()로 첫 번째 원소를 꺼낼 수 있는데 단지 이 부분만으로 시간 복잡도가 크게 감소하였다.

결과값2

---

그 외...

런너 풀이라는 정석적인 풀이 방식이 있는데 책만 보고 이해하는데 꽤나 시간이 걸렸다.

fast와 slow, 두 런너가 fast는 두 개씩, slow는 한 개씩 값들을 이동하는데 fast가 도착할 때 slow가 LinkedList의 중간지점까지 오므로 지금까지 값들의 역순과 앞으로의 값들을 비교해서 같으면 True, 다르면 False를 반환하는 방식이다.

 

러닝타임은 위의 데크 사용과 비슷하였다.