Palindrome Linked List

Problem Statement

Given the head of a singly linked list, return true if it is a palindrome, or false otherwise.

Example: Input: 1 → 2 → 2 → 1, Output: true

Approach 1: Copy to Array

Explanation: Store list values in an array and check palindrome using two pointers.

Time Complexity: O(n)

Space Complexity: O(n)

arr = []
while head != NULL:
    arr.append(head.val)
    head = head.next
left = 0, right = len(arr)-1
while left < right:
    if arr[left] != arr[right]:
        return false
    left++, right--
return true

Approach 2: Reverse Second Half

Explanation: Find middle, reverse second half, compare halves.

Time Complexity: O(n)

Space Complexity: O(1)

find middle of list
reverse second half
compare first and second half nodes
if all match:
    return true
else:
    return false