Palindrome Linked List Problem

Given the head of a singly linked list, write a function to determine if it is a palindrome. A palindrome is a sequence that reads the same forwards and backward.

Example 1:

Input: head = [1,2,2,1] Output: true Explanation: The linked list represents the sequence 1 -> 2 -> 2 -> 1, which is a palindrome.

Example 2:

Input: head = [1,2] Output: false Explanation: The linked list represents the sequence 1 -> 2, which is not a palindrome.

Constraints:

• The number of nodes in the list is in the range [1, 10^5]. Each node's value is between 0 and 9.

Your task is to implement a function that takes the head of a singly linked list as input and returns true if the list is a palindrome and false otherwise. Optimize your solution for both time and space complexity. Can you achieve O(n) time and O(1) space complexity? What are the edge cases to consider, such as an empty list or a single-node list?

# Palindrome Linked List

## Problem Description

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

## Naive Solution: Using an Array

1.  **Copy the Linked List to an Array:** Traverse the linked list and store the value of each node in an array.
2.  **Check for Palindrome:** Use two pointers, one at the beginning and one at the end of the array, to check if the array forms a palindrome.

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

def isPalindrome_naive(head: ListNode) -> bool:
    arr = []
    curr = head
    while curr:
        arr.append(curr.val)
        curr = curr.next
    
    left, right = 0, len(arr) - 1
    while left < right:
        if arr[left] != arr[right]:
            return False
        left += 1
        right -= 1
    return True

Time Complexity: O(n)

• Traversing the linked list to copy values to an array takes O(n) time.
• Checking the array for palindrome also takes O(n) time.

Space Complexity: O(n)

• We use an array to store the values of the linked list, which requires O(n) space.

Optimal Solution: Reverse the Second Half

This approach avoids the O(n) space complexity by reversing the second half of the linked list in place.

1. Find the Middle: Use the slow and fast pointer approach to find the middle of the linked list.
2. Reverse the Second Half: Reverse the linked list starting from the middle.
3. Compare: Compare the first half and the reversed second half to check for palindrome.
4. Restore the List: Reverse the second half again to restore the original list (optional, but good practice).

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


def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True

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

    # Reverse the second half of the linked list
    prev, curr = None, slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Compare the first half and the reversed second half
    first_half, second_half = head, prev
    result = True
    while second_half:
        if first_half.val != second_half.val:
            result = False
            break
        first_half = first_half.next
        second_half = second_half.next

    # Restore the linked list (optional)
    prev, curr = None, prev
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    slow.next = prev  # Connect the first half with the restored second half

    return result

Time Complexity: O(n)

• Finding the middle takes O(n/2) which is O(n)
• Reversing the second half takes O(n/2) which is O(n)
• Comparing the two halves takes O(n/2) which is O(n)

Therefore, the overall time complexity is O(n).

Space Complexity: O(1)

• We only use a few pointers, so the space complexity is constant.

Edge Cases

1. Empty List: If the list is empty, it is considered a palindrome.
2. Single Element List: A list with only one element is also a palindrome.
3. Even Length List: The algorithm works correctly for lists with an even number of nodes.
4. Odd Length List: The algorithm correctly handles lists with an odd number of nodes.

Visualization

Example: 1 -> 2 -> 2 -> 1

1. Initial List:

   Head -> 1 -> 2 -> 2 -> 1 -> None
   

2. Finding the Middle (Slow and Fast Pointers):

   Slow: 1 -> 2
   Fast: 1 -> 2 -> 1 (stops here)
   Middle: 2
   

3. Reversing the Second Half:

   Original Second Half: 2 -> 1 -> None
   Reversed Second Half: 1 -> 2 -> None
   

4. Comparing the First and Reversed Second Halves:

   First Half:  1 -> 2
   Second Half: 1 -> 2
   

5. Result: True (Palindrome)