13. Palindrome Linked List

🎯 leetcode - 234. Palindrome Linked List

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 13번 문제

📌 날짜

2020.01.24

📌 시도 횟수

1 try

💡 Code

# My Solution - List로 변환하여 풀기
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        node = head
        pal = []
        while node is not None:
            pal.append(node.val)
            node = node.next

        if pal == pal[::-1]:
            return True
        return False

💡 문제 해결 방법

- linked list의 모든 노드를 접근하면서 값들을 list로 옮겨 담았다.
- 그리고 list를 뒤집은 결과가 원 상태와 동일한 지 비교하여 팰린드롬을 판단했다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. Deque로 최적화하기

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

💡 새롭게 알게 된 점

- 파이썬에서 deque를 사용하기 위해서는...
q: Deque = collections.deque() 와 같이 사용하면 된다.

- deque를 이용하면 양방향 모두 O(1)으로 pop 가능하다. list보다 효율적이다!

---

📌 둘. 런너 이용하기🏃‍♀️🏃‍♂️

✔ 문제 해결 방법

1. slow 런너가 중간 지점에 도달하도록 fast, slow를 각각 2칸, 1칸씩 이동시킨다.
2. rev는 slow가 1칸씩 이동할 때마다 slow가 지나친 노드를 역방향으로 연결하여
역방향 연결 리스트를 만든다.
3. rev(역방향 연결 리스트)와 slow의 (절반 ~ 끝) 접근 값을 서로 비교하여 대칭을 확인한다.

✔ Code

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
        if fast:  # 연결리스트 짝수인 경우 fast 1칸 더 이동
            slow = slow.next

        # 팰린드롬 여부 확인
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next

        return not rev
        # 팰린드롬이 아니라면 while문 중간에 탈출하여 rev가 None이 아니므로 False임
        # 반면 정상적으로 while이 종료되었다면 rev가 None이므로 True임

💡 새롭게 알게 된 점

- 런너 기법에 대해 새롭게 알게 되었다.

런너 기법 🏃‍♀️🏃‍♂️

런너 기법 : 연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있음

---

• 연결리스트의 경우 중간 위치나 길이를 파악하는 데에 배열에 비해 상대적으로 복잡하다. (전체를 다 탐색해야 하므로 O(n)의 시간이 소요됨) 따라서 런너 기법을 사용한다.
• 보통 2개의 런너를 사용한다. 빠른 런너(fast runner)와 느린 런너(slow runner)
• 대개 빠른 런너는 두 칸씩 건너 뛰고, 느린 런너는 한 칸씩 이동하게 된다.
• 빠른 런너가 연결 리스트의 끝에 도달하면, 느린 런너는 정확히 연결 리스트의 중간 지점을 가리키게 된다.
• 이와 같은 방식으로 중간 위치를 찾아내면 중간 지점을 기준으로 값을 비교하거나 뒤집기를 시도하는 등 활용이 가능하다.