Palindrome Linked List

Intuition

Solution

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # Get length
        l = 0
        node = head
        while node:
            l += 1
            node = node.next

        # Split into 2 parts
        right = head
        if l <= 1:
            return True

        if l % 2 == 0:
            mid = head
            for i in range(l // 2 - 1):
                mid = mid.next
            left = mid.next
            mid.next = None
        if l % 2 == 1:
            mid = head
            for i in range(l // 2 - 1):
                mid = mid.next
            left = mid.next.next
            mid.next = None


        right = self._revert(right)

        while left:
            if left.val != right.val:
                return False
            left, right = left.next, right.next
        return True

    def _revert(self, node):
        pres = None
        head = node
        while head:
            # pop(0) from head
            tmp = head
            head = head.next
            tmp.next = pres
            pres = tmp

        return pres