[LeetCode] 234. Palindrome_Linked_list (Easy) 2023/5/4

문제 제목	정답률	난이도
234. Palindrome-Linked-list	50.3%	Easy

Palindrome Linked List - LeetCode

 

문제요약

단일 연결 리스트가 팰린드롬인지 판단하여라

조건 1) 단일 연결리스트의 헤더가 입력으로 주어진다

 

 

생각했던 풀이 1 : 연결리스트의 값을 배열에 넣어 팰린드롬 판단 (789ms)

배열에 삽입한 뒤, 슬라이싱 이용해 값을 비교

생각했던 풀이 2 : 데크(Deque)의 이중 연결 리스트 구조를 활용한 최적화 (837ms)

pop 함수를 이용해서 양쪽 원소를 비교

단, deque  자료형의 popleft 함수를 이용해서 pop(0)의 시간 복잡도인 O(n)을 O(1)로 최적화

발견한 새로운 풀이 3 : Runner 기법을 활용 (637ms)

Runner 기법은 '연결리스트스러운' 풀이를 위해 사용되며 빠른 러너와 느린 러너 2개의 포인터 이용

[파이썬 코딩테스트 개념] 1-1. 연결리스트 - 러너

 

 

풀이 1

배열에 값을 연결리스트에 값을 넣은 뒤, 팰린드롬 판단

 

Step1. 연결 리스트의 값을 배열에 저장

 

Step2. 팰린드롬 판단 -> 슬라이싱 이용

 

 

구현

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        linked_list=[]
        while head.next!=None:
            linked_list.append(head.val)
            head=head.next
        linked_list.append(head.val)

        if linked_list==linked_list[::-1]:
            return True
        return False

 

 

풀이 2

데크(deque) 자료형을 이용

 

Step1. 연결 리스트 값을 데크에 저장 -> collections.deque() 자료형 이용

 

Step2. 데크의 양쪽 연결 리스트 특성을 이용해 팰린드롬 확인 -> popleft(), pop() 함수 이용

 

 

구현

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        deque=collections.deque()

        while head.next!=None:
            deque.append(head.val)
            head=head.next
        deque.append(head.val)

        while len(deque)>1:
            if deque.popleft()!=deque.pop():
                return False
        return True

 

 

풀이 3 (637ms)

러너(Runner) 기법 활용해서 새로운 연결리스트(기존의 연결리스트를 역순으로 만드는) 만들어 비교

 

Step1. 러너 두 개 생성하여 기존의 연결리스트를 역순으로 만들기

 

Step2. 느린 러너와 역순 연결리스트를 이용해 팰린드롬 확인

 

 

구현

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        reverse_head=None
        slow=fast=head

        #러너를 이용해 역순 연결리스트 생성
        while fast and fast.next:
            #빠른 러너는 두칸씩 이동
            fast=fast.next.next
            reverse_head, reverse_head.next, slow=slow, reverse_head, slow.next
            #느린 러너는 한칸씩 이동
            
        if fast: #연결리스트의 노드의 수가 홀수이면 다음 노드로(가운데 값은 팰린드롬 비교 대상이 아님)
            slow=slow.next
        while reverse_head!=None:
            if reverse_head.val!=slow.val:
                return False
            reverse_head=reverse_head.next
            slow=slow.next
        return True

 

 

cf) 빠른 러너, 느린 러너, 역순 연결리스트의 방향과 방문경로 확인

 

연결리스트 길이가 홀수일 경우

 

홀수) 빠른 러너, 느린러너, 역순 연결리스트의 방향과 방문경로

 

 

연결리스트 길이가 짝수일 경우

 

짝수) 빠른 러너, 느린러너, 역순 연결리스트의 방향과 방문경로