234. Palindrome Linked List - python3

Given a singly linked list, determine if it is a palindrome.

My Answer 1: Accepted (Runtime: 72 ms - 51.63% / Memory Usage: 24.3 MB - 39.60%)

# 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:
        if head is None:
            return True
        if head.next is None:
            return True
        
        i = 0
        arr = []
        head2 = head
        
        while head2:
            arr.append(head2.val)
            head2 = head2.next
        arr.reverse()
        
        while head:
            if head.val != arr[i]:
                return False
            i += 1
            head = head.next
            
        return True

링크드 리스트가 아니라 그냥 배열 형태의 리스트였으면 절반으로 나눠서 비교하면 됐을텐데...
하는 생각으로 head 를 한번 훑으면서 arr 리스트에 모든 값을 넣고 reverse() 해주었다.
그러고 다시 head.val 과 arr 값의 비교 -> 다르면 무조건 False

짝수든 홀수든 대칭만 비교하면 된다.

근데 메모리도 더 쓰고 뭔가 매우 비효율적일 것만 같은 생각이 들어서...^^ 다른 사람의 답도 참고하기로 함

리스트를 reverse 할 수 있을까?!

Other Answer 1:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True

        val_arr = []
        while head:
            val_arr.append(head.val)
            head = head.next
        for i in range(len(val_arr) // 2 + 1):
            if val_arr[i] != val_arr[-(i + 1)]:
                return False
        return True

이사람은 나랑 비슷한 방식인데 96% 가 나왔다고 함
근데 내 컴에서 돌리면 51% 나옴;
이거 컴터마다 다른 런타임 아닌지...

Other Answer 2:

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

stack 을 이용한 방식

대체적으로 내 방식과 비슷하게 푸는듯?