LeetCode 234(Palindrome Linked List, Python)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 주어진 연결 리스트가 팰린드롬(좌우 뒤집어 같은 것)인지 확인하여 True 또는 False를 반환

3. 처음 풀이

• head의 값을 리스트에 하나씩 추가한 후 그 리스트와 역순이 같으면 대칭
• 물론 linked list를 그 자체로 풀지 않고 array로 바꾸어 풀었기 때문에 치팅이라고 생각함. 하지만 연결 리스트 자체에서 중간을 찾는 방법을 떠올리지 못함. 

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

4. 다른 풀이

• two pointers를 출발시키고 fast는 두 칸 씩, slow는 한 칸 씩 이동. fast가 끝에 도달하면 slow는 중앙에 위치함.
• slow를 마저 이동시키며 중간 이후 절반을 prev에 저장
• head와 prev의 값을 비교하여 다른 것이 나오면 False, prev가 끝날 때까지 같으면 True

class Solution:
		def isPalindrome(self, head):
		    # 중간 지점 찾기
		    slow = fast = head
		    while fast and fast.next:
		        slow = slow.next
		        fast = fast.next.next
		
		    # 중간 이후 노드들 역순으로 만들기
		    prev, curr = None, slow
		    while curr:
		        temp = curr.next
		        curr.next = prev
		        prev = curr
		        curr = temp
		
		    # 비교
		    while prev:
		        if head.val != prev.val:
		            return False
		        head = head.next
		        prev = prev.next
		
		    return True

5. 배운 점

• 와 이렇게 가운데를 찾을 수 있구나…