[leetcode/python] 234번 Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

문제 요약 : 연결 리스트가 패린드롬(앞뒤로 읽어도 같은 값)인지 검증해라

 

로직은 다음과 같다.

1. 연결 리스트를 돌면서, 현재 값을 origin에 쭉 저장하고, 순서를 반대로 해서  reverse에 저장한다.

2. 두개가 같은지 비교해서 리턴한다.

 

# 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:
        origin = ''
        reverse = ''
        node = head

        while node:
            origin = origin + str(node.val)
            reverse = str(node.val) + reverse
            node = node.next

        return origin == reverse

시간복잡도는 O(n)이다