Palindrome Linked List

""" 
펠린드롬

토마토, 기러기

전체 문자열의 가운데를 중심으로 A,B 로 나누었을 때 
A 의 역순이 B 와 같은 문자열인 문자열

1->2->2->1 

전체 길이가 4이면
반복문을 2번 돌림

연결리스트를 2번 이동해서 2->1-> None 인 연결리스트를 뽑아냄

1->2 를 역순으로 하는 연결리스트( 2->1-> None  )를 뽑아냄

둘이 같은지 확인함 

같으면 펠린드롬이고 아니면 펠린드롬이 아님
 """

# 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: ListNode) -> bool:

        fast = head
        slow = head
        rev = None
        result = True

        while fast and fast.next:
            fast = fast.next.next

            # slow 를 임시저장
            # temp = 1->2->2-> 1
            temp = slow
            # slow 를 slow next 로 변경
            # slow = 2->2->1
            # slow 참조를 temp 에 연결한 뒤
            # slow 참조를 다시 변경
            slow = slow.next
            # temp = 1-> None
            temp.next = rev
            # rev = 1-> None
            rev = temp

        # 입력 리스트가 홀수일 경우
        # 1->2->0->2->1
        # slow = 2->1 -> None 이 되어야 함
        # 반복문 만으로는 0 -> 2-> 1-> None 이 됨
        # 홀수 일때는 한칸 더 이동해줘야 함
        # next 는 없지만 val 은 있을 때 slow 한칸 더 이동
        if fast:
            slow = slow.next

        while rev:
            if rev.val != slow.val:
                result = False
                break

            rev = rev.next
            slow = slow.next

        return result