[LeetCode] Palindrome Linked List 파이썬

class Solution:
    # @param {ListNode} head
    # @return {boolean}
    def isPalindrome(self, head):
        # get mid point
        cur = head
        N = 0
        while cur:
            N += 1
            cur = cur.next
        mid = N//2
        i = 0
        
        def reverse(head):
            ans = None
            while head:
                nx = head.next
                head.next = ans
                ans = head
                head = nx
            return ans
        
        first = second = head
        # to mid point
        while i < mid:
            second = second.next
            i += 1
        second = reverse(second)
        
        # check palindrome
        while first and second:
            if first.val != second.val:
                return False
            first = first.next
            second = second.next
        return True

1. mid 지점을 찾은 다음

 

2. first, second 를 mid 까지 이동시킨다 (i < mid 조건을 줌으로써 짝수, 홀수 상관없이 도착할 수 있도록)

ex.

5개일 경우

mid = 2(5//2)

[0,0,0,0,0] 에서 zero index(i=0부터) 했기 때문에 0,0까지만 진행 되도록

6개일 경우

mid = 3(6//2)

[0,0,0,0,0,0] 에서 zero index(i=0부터) 했기 때문에 0,0,0까지만 진행 되도록

 

3. second를 reverse 함수를 통해 reverse 시킨 후 , first와 second를 비교하면서 palindrome 여부를 확인한다

 

 

 

 

www.youtube.com/watch?v=cFLTe6hC0-o