[코딩인터뷰] 연결리스트 - 팰린드롬 연결리스트 문제풀이

문제

연결리스트가 팰린드롬인지 체크해라. 팰린드롬이란, 거꾸로 해도 같은 문자를 뜻한다.

 

입력 [1 -> 2] : False
입력 [1 - > 2 -> 2 -> 1] : True

 

 

 

 

나의코드

# 연결리스트가 팰린드롬인지 체크 (팰린드롬이란, 거꾸로해도 같은 문자)

# 입력 1-> 2 : false
# 입력 1->2->2->1 : true
from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 리스트 변환
def isPalindrome(self, head: ListNode) -> bool:
    # 노드가 1개일 경우 - 팰린드롬
    if head.next is None:
        return True

    list = []

    # 연결리스트를 리스트로 변환
    while head is not None:
        # value append
        list.append(head.val)

        # 다음 노드의 값을 저장
        head = head.next

        print(list)

    # 리스트와 역순리스트 비교
    if list == list[::-1]:
        return True
    else:
        return False

 

처음에 생각했던 방법은 연결리스트를 뒤집거나 이중 반복문을 사용하여 처음부터 시작하는 노드와 마지막에서 시작하는 노드를 비교하는 방법이였다. 하지만 단순히 팰린드롬을 체크하는데에 너무 많은 시간이 소요되는 것 같아서 연결리스트를 리스트로 변환 후, 리스트를 체크하는 방법으로 구현하였다.