visual walkthrough
Palindrome Linked List
Combines finding the middle with reversing the second half.
The idea
A palindrome needs the first value compared with the last, but a singly linked list only goes forwards.
So turn the second half around: find the middle with slow and fast pointers, reverse from there, then walk inwards from both ends.
Complexity
| approach | time | space |
|---|---|---|
| Copy to an array | O(n) | O(n) |
| Reverse the second half | O(n) | O(1) |