[LeetCode] 234. Palindrome Linked List

문제 :

 

 

문제는 간단하다. 입력값으로 연결 리스트가 주어지고, 이 연결 리스트가 회문인지 판단하는것이다.

 

먼저, 이 문제를 해결하기 전에 알아야 할 것이 있다.

 

-여기서 head는 리스트가 아니라 '연결 리스트' 이다. 그래서 이 연결 리스트를 뒤집어 리스트로 반환한 후, head와 비교가 불가능하다(타입 불일치).

 

아래는 내가 제출해 통과한 코드이다.

# 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:
        stk = []
        curr = head
        while curr:
            stk.append(curr.val)
            curr = curr.next
        reversed_list = stk[::-1]
        return stk == reversed_list

 

-먼저, 나는 스택을 이용해 주었다. 연결 리스트를 순회하며 스택에 차례대로 val들을 담아준다. 여기서 이 연결 리스트는 단방향 연결 리스트이므로 연결 리스트의 왼쪽 값부터 차례로 스택에 들어갈 것이다.

 

- while curr : curr(head를 참조하는 연결 리스트)이 빌때까지 계속 

 

-stk.append(curr.val) : 여기서 curr.val을 append해주어야 연결 리스트의 한개의 노드가 정상적으로 들어가고, 그냥 curr만 넣는다면 head의 모든 값이 담길 것이다.

 

- curr = curr.next를 통해 curr을 다음 노드의 값으로 업데이트 해 준다. 이런 식으로 while문을 순회하며 연결 리스트의 모든 값들을 스택에 넣어 준다.

 

- reversed_list = stk[::-1] : 이제, 슬라이싱을 이용해 스택을 뒤집는다.

 

-이후, 우리가 위에서 쌓은 스택과 방금 뒤집은 스택을 비교해 회문인지 판단한다.

 

  💬

스택만 생각 해낸다면, 생각보다 쉽게 풀릴 문제였다. 하지만 보자마자 연결 리스트라 지레 겁을 먹었다. ("단방향 연결 리스트를 어떻게 뒤에서부터 순회하지?") => 스택을 사용해 앞에서부터 하나씩 순회하면 되는구나!

 

파이썬에서 스택은 실제로 별도의 자료형이 없으며, 대신 리스트를 사용하여 스택의 기능을 구현할 수 있다. 리스트의 append 메서드와 pop 메서드를 사용하여 스택과 같은 LIFO(Last In, First Out) 동작을 수행할 수 있다. 따라서 파이썬에서 스택이라고 언급할 때, 일반적으로 리스트를 사용하여 구현된 스택을 의미한다.