Given a singly linked list, determine if it is a palindrome in O(n) time and O(1) space. Examples: `... Interview Question for Netflix

## Palindrome Linked List

### Problem Description

You are given a singly linked list. Write a function to determine if the linked list is a palindrome. Implement this in O(n) time and O(1) space.

**Example:**

List: 1 -> 2 -> 2 -> 1

Output: true

List: 1 -> 2 -> 3 -> 2 -> 1

Output: true

List: 1 -> 2 -> 3 -> 4

Output: false

**Constraints:**

*   The number of nodes in the list is in the range `[1, 5 * 10^5]`.
*   `0 <= Node.val <= 9`

**Follow up:**

Could you do it in O(n) time and O(1) space?


### Naive Solution (O(n) time, O(n) space)

A simple approach is to traverse the linked list and store the values in an array. Then, check if the array is a palindrome.

```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
    
    return values == values[::-1]

Optimal Solution (O(n) time, O(1) space)

To achieve O(n) time and O(1) space complexity, we can use the following approach:

Find the middle of the linked list using the slow and fast pointer technique.
Reverse the second half of the linked list.
Compare the first half and the reversed second half.
Reverse the second half back to its original state (optional, but good practice).

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


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

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

    # 2. Reverse the second half
    second_half_head = slow
    prev = None
    current = second_half_head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    reversed_second_half_head = prev

    # 3. Compare the first half and the reversed second half
    first_half_head = head
    while reversed_second_half_head:
        if first_half_head.val != reversed_second_half_head.val:
            
            # reverse second half back
            prev = None
            current = prev

            return False
        first_half_head = first_half_head.next
        reversed_second_half_head = reversed_second_half_head.next

    # reverse second half back
    prev = None
    current = prev

    return True



# Helper function to create a linked list from a list of values
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for i in range(1, len(values)):
        current.next = ListNode(values[i])
        current = current.next
    return head


# Example usage:
list1 = create_linked_list([1, 2, 2, 1])
print(f"List 1 is palindrome: {is_palindrome(list1)}")  # Output: True

list2 = create_linked_list([1, 2, 3, 2, 1])
print(f"List 2 is palindrome: {is_palindrome(list2)}")  # Output: True

list3 = create_linked_list([1, 2, 3, 4])
print(f"List 3 is palindrome: {is_palindrome(list3)}")  # Output: False

list4 = create_linked_list([1])
print(f"List 4 is palindrome: {is_palindrome(list4)}")  # Output: True

list5 = create_linked_list([1,2])
print(f"List 5 is palindrome: {is_palindrome(list5)}")  # Output: False

Big O Runtime Analysis

Finding the Middle: Traversing the linked list to find the middle takes O(n) time.
Reversing the Second Half: Reversing the second half of the linked list takes O(n/2) which simplifies to O(n) time.
Comparing the Halves: Comparing the first half and the reversed second half takes O(n/2) which simplifies to O(n) time.
Reversing the Second Half Back (Optional): This also takes O(n) time.

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

Big O Space Usage Analysis

The algorithm uses a constant amount of extra space, regardless of the size of the linked list. We only use a few pointers (slow, fast, prev, current, etc.). Thus, the space complexity is O(1).

Edge Cases

Empty List: An empty list is considered a palindrome.
Single Node List: A list with only one node is also considered a palindrome.
List with Two Nodes: The algorithm correctly handles lists with two nodes.
Even Length List: The algorithm correctly handles lists with an even number of nodes.
Odd Length List: The algorithm correctly handles lists with an odd number of nodes.