234. Palindrome Linked List

Solution 1: Auxiliary array & reversed

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        numsArr = []
        while head:
            numsArr.append(head.val)
            head = head.next
        return numsArr == numsArr[::-1]

Time Complexity: O(N)
Space Complexity: O(N)

Solution 2: Reverse first half list

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        prevNode = None
        slowPtr, fastPtr = head, head
        while fastPtr and fastPtr.next:
            backupSlowPtr = slowPtr
            # i. To partition two part of list
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
            # ii. To reverse first half of list
            backupSlowPtr.next = prevNode
            prevNode = backupSlowPtr
        # The len of list must be odd, we skip compareing the central [N // 2] node
        if fastPtr:
            slowPtr = slowPtr.next
            
        # Compare the reversed first half and last half
        while slowPtr and prevNode:
            if slowPtr.val != prevNode.val:
                return False
            slowPtr = slowPtr.next
            prevNode = prevNode.next

        return True

Time Complexity: O(N)
Space Complexity: O(1)

Solution 3: Reverse first half list & restore original

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        prevNode = None
        slowPtr, fastPtr = head, head
        while fastPtr and fastPtr.next:
            backupSlowPtr = slowPtr
            # i. To partition two part of list
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
            # ii. To reverse first half of list
            backupSlowPtr.next = prevNode
            prevNode = backupSlowPtr
        # The len of list must be odd, we skip compareing the central [N // 2] node
        if fastPtr:
            slowPtr = slowPtr.next
            
        # Compare the last half list and first half (reversed) list 
        prevNode = slowPtr
        while slowPtr and backupSlowPtr:
            if slowPtr.val != backupSlowPtr.val:
                return False
            slowPtr = slowPtr.next

            # NOTE: We want to restore the list originally
            backupNext = backupSlowPtr.next
            backupSlowPtr.next = prevNode
            prevNode = backupSlowPtr
            backupSlowPtr = backupNext

        return True

Time Complexity: O(N)
Space Complexity: O(1)

Solution 4: Recursive + global var

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        def checkPalin(node):
            if not node:
                return True
            
            global frontNode
            # The node pointer will first go to the end, and check for the front & tail node, then stack up to the previous caller 
            # e.g, (Front) "1" -> 2 -> 3 -> 3 -> 2 -> "1" (Tail)
            isTailPalin = checkPalin(node.next)
            isFrontAndTailEqual = frontNode.val == node.val
            
            # Check for the next pair
            # e.g, 1 -> (Front) "2" -> 3 -> 3 -> "2" (Tail) -> 1
            frontNode = frontNode.next
            
            return isTailPalin and isFrontAndTailEqual
        
        # Main
        global frontNode
        frontNode = head
        ans = checkPalin(head)
        return ans

Time Complexity: O(N) // O(1) compare value & O(N) recursive call
Space Complexity: O(N) // The recursive call stack

Reference

https://leetcode.com/problems/palindrome-linked-list/discuss/64500/11-lines-12-with-restore-O(n)-time-O(1)-space
https://leetcode.com/problems/palindrome-linked-list/discuss/2466602/Python3-different-approachesDetailed-Explantion-or-Easy-understand-or-Beginner-friendly-_