[LeetCode] 234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

Palindrome Linked List - LeetCode

Single Linked List 문제이다.

내 풀이

리스트를 이용한 풀이이다.
Deque으로도 가능하다.

from typing import List
# 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: ListNode) -> bool:
        list: List = []

        if not head:
            return True

        # 리스트에 담기
        node = head
        while node != None:
            list.append(node.val)
            node = node.next

        if list == list[::-1]:
            return True
        else:
            return False

이렇게 풀면 간단하게는 가능하지만 연결리스트 문제라는 취지엔 맞지 않는다.

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

라고 되어 있으므로, O(1)으로 풀 수 있는 방법을 생각해 내야 한다.

공부 한 풀이

파이썬 알고리즘 인터뷰(p.209) 의 runner기법 의 설명이 잘 이해가 가질 않아서, 다른 풀이들을 좀 찾아봤다.

• Runner기법 (Python)
• Runner기법 (JavaScript)

유튜브 강의들인데, 설명이 잘 나와있어서 링크한다.

from typing import List


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow, fast = head, head

        # find middle (slow)
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # reverse
        rev = None
        while slow:
            tmp = slow.next
            slow.next = rev
            rev = slow
            slow = tmp

        # check palindrome
        left, right = head, rev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

 two-point기법과 비슷 하지만, 다르다. Single Linked List는 단방향으로만 포인터를 이동할 수 있기 때문에, 역순으로 탐색하기가 어렵다.

 

첫번째 while 루프가 끝나면, slow포인터는 middle로, fast포인터는 끝을 가리기케 된다.

# find middle (slow)
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

이렇게 Runner기법은  속도가 다른 두 포인터를 이용해서 문제를 푸는 것인데, 주로 단방향 연결리스트 (Single Linked List)에서 많이 사용된다.

 

참고자료

• Linked lists and the Runner Technique | by Jay Prakash | Medium

• 파이썬 알고리즘 인터뷰 책

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기