[Leetcode]234. Palindrome Linked List

2024. 7. 21. 10:56Algorithm

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        def recursive_check(current: ListNode) -> bool:
            nonlocal front_pointer
            
            if current is not None:
                if not recursive_check(current.next):
                    return False
                if current.val != front_pointer.val:
                    return False
                front_pointer = front_pointer.next
            
            return True
    
        front_pointer = head
        return recursive_check(head)

1. 문제:

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

 

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?

 

2. 풀이:

첫 번째, reversed 방법을 사용하는 거다. 예를 들어, 4개의 element가 있는 linked_list가 있을 때, 반으로 나누어 앞에 2개의 element를 reversing 시킨다. 그리 고난 후, 뒤에 있는 2개의 linked_list와 비교한다. 똑같으면, 계속 진행하고 loop가 끝나면 return True를 시킨다. 똑같지 않다면, return False를 시킨다. 이때, 나는 linked_list의 길이를 알기 위해 count = 0을 두고, while loop를 돌려, 길이를 알아냈다. 하지만, slow = 0 , fast = 0 을 두고 fast는 fast.next.next , slow는 slow.next를 두어, 길이를 알아내는 방법도 있다는 것을 배웠다. 

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head.next is None or head is None:
            return True 
        count = 0 
        temp = head 
        while head:
            count += 1 
            head = head.next 
        current = temp 
        before = None 
        after = current  
        for i in range(count //2):
            after = after.next 
            current.next = before 
            before = current 
            current = after 
        if count % 2 != 0:
            current = current.next 
        while before is not None: 
            if before.val == current.val:
                before = before.next 
                current = current.next 
            else:
                return False 
        return True

 

두 번째, Stack을 이용한풀이다. 

이 풀이는 발상자체는 좋으나, current_node와 stack을 전부 비교하는 loop를 돌린다는 점이 흠이다. 

물론, 이 부분을 개선할 수도 있다고 생각한다. 

class Solution:
    def isPalindrome(self, head) -> bool:
        stack = []
        current_node = head 
        while head is not None:
            stack.append(head.val) 
            head = head.next  
        while current_node:
            if current_node.val != stack.pop():
                return False 
            current_node = current_node.next 
        return True

개선하면 이렇게 고칠 수 있다. 첫 번째로, 홀수일 때와 짝수일 때로 나눈다. 이때 stack list를 이용하기 때문에 length 구하기는 용이하다. 

class Solution:
    def isPalindrome(self, head) -> bool:
        stack = []
        current_node = head 
        fast_node = current_node 
        while head is not None:
            stack.append(head.val) 
            head = head.next 
        stack_len = len(stack) 
        if stack_len % 2 == 0:
            while fast_node:
                if current_node.val != stack.pop():
                    return False 
                current_node = current_node.next 
                fast_node = fast_node.next.next 
            return True 

        else:
            while fast_node.next:
                if current_node.val != stack.pop():
                    return False 
                current_node = current_node.next 
                fast_node = fast_node.next.next 
            return True

 

코드가 지저분해진다. 하지만 불필요한 계산은 줄일 수 있으니, 더 좋을지도 모르겠다. 

 

세 번째, 재귀코드다. 

chat gpt 4o에게 물어본 코드다. 코드가 아름답다. 

 

'Algorithm' 카테고리의 다른 글

[Leetcode]203. Remove Linked List Elements  (0) 2024.07.22
Hanoi top  (2) 2024.07.21
[Leetcode]21. Merge Two Sorted Lists  (2) 2024.07.20
[Leetcode]509. Fibonacci Number  (0) 2024.07.19
[Leetcode]206. Reverse Linked List  (0) 2024.07.17