Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise. The number of nodes in the list is in the range [1, 10<sup>5</sup>]. Node values are between 0 and 9. Solve it in O(n) time and O(1) space.

Example 1: Input: head = [1,2,2,1] Output: true

Example 2: Input: head = [1,2] Output: false

# Palindrome Linked List

## Problem Description

Given the head of a singly linked list, determine if it is a palindrome.

**Example 1:**

Input: `head = [1,2,2,1]`
Output: `true`

**Example 2:**

Input: `head = [1,2]`
Output: `false`

## Naive Approach (Using Extra Space)

1.  Traverse the linked list and store the values in an array.
2.  Check if the array is a palindrome using two pointers (one at the beginning and one at the end).

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next



def is_palindrome_naive(head):
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next

    left, right = 0, len(values) - 1
    while left < right:
        if values[left] != values[right]:
            return False
        left += 1
        right -= 1
    return True

Optimal Approach (O(1) Space)

1. Find the middle of the linked list using the slow and fast pointer approach.
2. Reverse the second half of the linked list.
3. Compare the first half and the reversed second half.
4. Reverse the second half back to its original form (optional, but good practice).

def is_palindrome_optimal(head):
    if not head or not head.next:
        return True

    # Find the middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half
    second_half = slow
    prev, current = None, second_half
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    second_half_reversed = prev

    # Compare the first half and the reversed second half
    first_half = head
    while second_half_reversed:
        if first_half.val != second_half_reversed.val:
            return False
        first_half = first_half.next
        second_half_reversed = second_half_reversed.next

    return True

Big O Runtime Analysis

• Naive Approach: O(n) for traversing the linked list + O(n) for checking the array = O(n)
• Optimal Approach: O(n) for finding the middle + O(n/2) for reversing the second half + O(n/2) for comparing = O(n)

Big O Space Usage Analysis

• Naive Approach: O(n) because we store the linked list values in an array.
• Optimal Approach: O(1) because we only use a few pointers.

Edge Cases

1. Empty list: Should return True.
2. Single element list: Should return True.
3. List with two elements: Should correctly identify if it's a palindrome.
4. List with an odd number of elements: Should correctly handle the middle element.

Here's how edge cases are handled in the optimal solution:

• An empty or single-element list is immediately handled at the beginning of the is_palindrome_optimal function.
• When the fast pointer reaches the end of the list in the while loop (while fast and fast.next), the slow pointer will be at the middle node for lists with odd number of nodes, and the first node of the second half for list with even number of nodes. This is why second half of the linked list is correctly reversed.