[LeetCode] 234. Palindrome Linked List 팰린드롬 연결리스트

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

234번 Palindrome Linked List 는 연결 리스트가 팰린드롬 구조인지 판별하는 문제이다.

 

* 펠린드롬 : 앞뒤가 똑같은 단어나 문장 

 

 

# 풀이방법 1 - value값 리스트 저장 후 판별 (내 풀이)

# 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:
 
        values = []
    
        node = head 
        # 1. 연결리스트를 순회하며 노드의 값들을 리스트에 저장한다.
        while node is not None :
            values.append(node.val)
            node = node.next
        
		# 2. 노드를 저장한 리스트를 거꾸로 뒤집어 펠린드롬인지 확인한다.
        if values == values[::-1]:
            return True
        else :
            return False

1. 연결리스트를 순회하며 노드의 값들을 리스트에 저장한다.

2. 노드를 저장한 리스트를 거꾸로 뒤집어 펠린드롬인지 확인한다.

 

 

# 풀이 방법 2 - 런너를 활용한 풀이(책 풀이 참고)

* 런너 기법 : 연결 리스트를 순회할 때 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:
 
        rev = None
        slow = fast = head
        
        # 런너 이용 
        while fast and fast.next : 
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next

        if fast : 
            slow = slow.next
            
        # 펠린드롬 판별
        while rev and rev.val == slow.val:
            rev = rev.next
            slow = slow.next
            
        return not rev

| 아이디어  | 

fast와 slow 런너를 이용하여 판별. 

- fast 런너는 2개씩 노드를 건너뛰고, slow 런너는 1개씩 노드를 이동한다. 이때 slow런너가 이동할 때, 역순으로 연결리스트 rev를 만든다. 

- 결과적으로 slow 런너에는 중간지검까지의 연결리스트가, rev 리스트에는 slow로 이동한 중간지점까지의 역순 연결 리스트가 남게된다.  

 

| 흐름 | 

1. 런너를 이용하여 역순 연결 리스트 구성 

- slow와 fast 런너 모두 head로 시작하고, fast는 2칸 slow는 1칸씩 이동한다.

- 입력값이 홀수인 경우에는 중앙값이 존재하므로 slow런너가 앞으로 한 칸 더 이동해야된다.

2. rev와 slow 리스트를 통해 팰린드롬 여부를 확인

 

 

| 핵심 |

# 런너 이용 
        while fast and fast.next : 
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next

 

 

# 결과