Linked Palindrome

Return true if the linked list reads the same forwards and backwards (by value). An empty list is a palindrome.

ListNode:
    value
    next   // reference to the next node, or nothing if this is the last one

linkedPalindrome(head)

Input format: space-separated node values.

Examples

1 → 2 → 1        // → true
1 → 2 → 2 → 1    // → true
1 → 2 → 3        // → false

Walkthrough

Thinking it through

Checking a palindrome is classic two-pointer: compare first with last, second with second-to-last, moving inward until the pointers cross. Easy with an array, since any index is reachable instantly. A singly linked list can't do that — only 'next' exists, never 'previous.' That mismatch between what two-pointer wants (access from both ends) and what the list offers (forward-only) is the crux here.

Why you can't just two-pointer the list directly

With an array, nums[i] and nums[j] are both O(1) regardless of position. With a linked list, walking backward from the tail isn't possible without extra memory or restructuring — there's no way to get a pointer to the last node and move it backward.

The straightforward fix: capture random access first

If forward-only traversal is all you have but the algorithm needs backward access too, do one forward pass copying every value into an array. Once values live in an array, the two-pointer check works exactly as it would for any sequence: one pointer front, one back, stepping toward each other, comparing at each stop.

Why this works and when it's good enough

One pass to build the array (O(n)), then a second pass over at most half the array to compare (O(n) worst case). Holding every value means O(n) space too — a reasonable trade for something simple and obviously correct.

There's a more memory-frugal technique — find the middle with slow/fast pointers, reverse the second half in place, compare against the first half — getting space to O(1) at the cost of temporarily mutating the list. Good next step once the simple version feels natural, but copy-to-array separates the two concerns (getting random access, then comparing) instead of solving both at once.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.