Palindromic Linked List

Copying all values into a Python list and checking values == values[::-1] works in O(n) time but uses O(n) extra space. The O(1) space approach reuses the reversal idiom from earlier in this subject:

1. Find the middle of the list using the classic slow/fast "runner" two-pointer technique — slow advances one node per step, fast advances two, so when fast reaches the end, slow is at the midpoint.
2. Reverse the second half of the list in place (same rewiring loop as the Linked List Reversal problem).
3. Walk the first half and the reversed second half together, comparing values; if any pair differs, it's not a palindrome.
4. (Optional but polite) reverse the second half back and reattach it, restoring the original list structure.

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

def is_palindrome(head: ListNode | None) -> bool:
    if head is None or head.next is None:
        return True

    # Step 1: find the middle with slow/fast pointers.
    slow, fast = head, head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next

    # Step 2: reverse the second half, starting after slow.
    def reverse(node):
        prev = None
        while node is not None:
            nxt = node.next
            node.next = prev
            prev = node
            node = nxt
        return prev

    second_half = reverse(slow.next)

    # Step 3: compare first half against reversed second half.
    first, second = head, second_half
    is_pal = True
    while second is not None:
        if first.val != second.val:
            is_pal = False
            break
        first = first.next
        second = second.next

    # Step 4 (optional): restore the list.
    slow.next = reverse(second_half)

    return is_pal

Complexity: O(n) time — finding the middle, reversing half the list, and comparing are each O(n) or less. O(1) extra space, since the reversal is done in place and only a constant number of pointers are used.