[Leetcode]234. Palindrome Linked List
2024. 7. 21. 10:56ㆍAlgorithm
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 |