[연결리스트] 13 팰린드롬 연결 리스트(Palindrome Linked List)

<LeetCode 문제>

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

Palindrome Linked List - LeetCode

연결 리스트가 팰린드롬 구조인지 판별하는 문제입니다.

<풀이>

연결 리스트에서 값을 뽑아 리스트에 넣어준 후, 슬라이싱을 통해 원본 리스트가 뒤집은 리스트와 같은지 비교했습니다.

  
# 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:
        num_list=[] #연결리스트에서 값들만 빼서 저장할 리스트
        
        while head!=None: #다음 연결리스트가 없을때까지
            num_list.append(head.val)
            head = head.next
            
        return num_list == num_list[::-1] #뒤집어서 같은지(O(N))

 

리스트 슬라이싱으로 뒤집는 게 아니라 Deque구조를 통해 앞, 뒤에서 값을 비교해나갈 수도 있습니다.

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        q: Deque = collections.deque() #deque 선언
        
        if not head: #빈 연결리스트일때
            return True
        
        node = head
        while node != None:
            q.append(node.val)
            node = node.next
        
        while len(q)>1:
            if q.popleft() != q.pop():
                return False #하나라도 앞,뒤 대칭되는위치에 다른게 있으면 False
            
        return True

 

추가로 Runner 기법을 통해 우아한 풀이도 가능합니다.

빠른 런너가 끝에 다다를 때 느린 런너는 정확히 중간 지점에 도달하게 되며, 느린 런너는 중간까지 이동하면서 역순으로 연결 리스트 rev를 만들어 나갑니다.

그리고 중간에 도달한 느린 런너가 나머지 경로를 이동할 때, 역순으로 만든 연결 리스트의 값들과 일치하는지 확인해나갑니다.

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None #역순 연결 리스트
        slow=fast=head #시작할때는 모두 head에서
        
        #런너를 이용해 역순 연결 리스트 구성
        while fast and fast.next:
            fast = fast.next.next #두칸씩 이동
            rev,rev.next,slow = slow,rev,slow.next #한칸씩 이동
        if fast:
            slow=slow.next #입력값 홀수일때 slow 한칸 더 앞으로 이동
        
        #팰린드롬 여부 확인(slow의 나머지 이동경로와 rev 비교)
        while rev and rev.val == slow.val:
            slow,rev = slow.next,rev.next
        return not rev

 

<학습내용>

1.  파이썬에서 linked list 표현 방법

<학습이 필요한 내용>

1. Runner 기법 제대로 습득필요
2. 파이썬 다중 할당 헷갈리는 부분 정리

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/Python_Study/08_linked_list/LC_234.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++