[Leetcode/Python] Palindrome Linked List

Top Interview Questions 의 Easy Collection에 있는 문제입니다.     
문제는 여기서 볼 수 있습니다.

 

Given the head of a singly linked list, return true if it is a palindrome.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

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

 

Code:

from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# case 1 : 끝까지 확인해 리스트에 value 넣고 체크하기
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        node2list = []
        # 처음부터 끝까지 확인해 리스트에 value값을 넣는다
        while head:
            node2list.append(head.val)
            head = head.next
        # 팰린드롬인지 확인한다.
        if node2list == node2list[::-1]:
            return True
        else:
            return False

# case 2 : Reversed first half == Second half?

"""
Phase 1: Reverse the first half while finding the middle.
Phase 2: Compare the reversed first half with the second half.
*link: https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/772/discuss/64500/11-lines-12-with-restore-O(n)-time-O(1)-space
"""
class Solution:
    def isPalindrome(self, head: Optional[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 = slow.next
            rev = rev.next
        return not rev

# case 1

- 가장 간단한 방법으로, 모든 노드를 확인 후 문제를 푼다

 

# case 2

- 노드의 크기가 짝수인지 홀수인지를 체크하는 용도로 fast 리스트노드를, 팰린드롬 확인용으로 rev, slow 리스트노드를 만들어 문제를 푼다.

 

링크드 리스트에서 fast, slow 리스트 두 개를 만들어 문제를 푸는 경우가 꽤 많은 것 같다.