문제 설명

Singly-linked list가 주어졌을 때, 해당 링크드 리스트가 palindrome인지 아닌지 여부 판단.
Palindrome: 거꾸로 뒤집어도 똑같은 경우
문제 출처: https://leetcode.com/problems/palindrome-linked-list/

문제 풀이

1차 문제 풀이

# 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: Optional[ListNode]) -> bool:
        a = []
		cur_node = head

        while cur_node:
            a.append(cur_node.val)
            cur_node = cur_node.next

        if a == list(reversed(a)):
            return True

        return False

간단히 파이썬 리스트를 생성해 value들을 append하여 뒤집어도 같은지로 판단할 수 있다. 하지만 Follow up에 O(n) time complexity와 O(1) space로 풀 수 있는지 적혀 있는 것을 보고 공간 효율적으로 코드를 작성해보기로 했다.

2차 문제 풀이

NeetCode - Palindrome Linked List - Leetcode 234 - Python를 참고해 코드를 작성했다.

# 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: Optional[ListNode]) -> bool:
        fast = head
        slow = head

        # find middle -> slow
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        # reverse second half
        prev = None
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp

        # check palindrome
        l, r = head, prev
        while r:
            if l.val != r.val:
                return False
            l = l.next
            r = r.next
        return True

1) fast pointer는 두 칸씩, slow pointer는 한 번씩 노드를 건너뛰며 slow pointer가 중간에 도달할 수 있도록 한다.
2) 중간에 도달한 slow pointer를 통해 second half를 뒤집는다.
3) 시작 지점과 끝 부분부터 차례대로 비교해가며 palindrome인지 확인한다.

전체적인 흐름을 알 수 있도록 예시도 첨부합니다.

성능 비교

1차 문제 풀이 성능

2차 문제 풀이 성능