1. Palindrome Linked List (LeetCode)
Model answer
The task
Determine whether a singly linked list reads the same from front to back and back to front. Return a boolean without relying on access to nodes by index.
Key idea
Find the midpoint with slow and fast pointers, then reverse the second half. Compare the two halves node by node; reverse the second half again afterward to restore the original list.
Approach
- Advance
slowby one node andfastby two untilfastreaches the end. - For an odd-length list, move the start of the second half past the middle node.
- Reverse the second half in place.
- Compare corresponding values from the head and reversed second half.
- Restore the second half before returning the result.
class Solution:
def isPalindrome(self, head):
def reverse(node):
previous = None
while node:
following = node.next
node.next = previous
previous = node
node = following
return previous
slow = fast = head
# Find the midpoint. For odd length, fast ends on the final node.
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Skip the middle node when the list has odd length.
second_half_start = slow.next if fast else slow
reversed_half = reverse(second_half_start)
# Compare the first half with the reversed second half.
left = head
right = reversed_half
is_palindrome = True
while right:
if left.val != right.val:
is_palindrome = False
break
left = left.next
right = right.next
# Restore the list to its original structure.
reverse(reversed_half)
return is_palindrome
Complexity:
- Time: O(n), to find the midpoint, reverse, compare, and restore.
- Space: O(1), using only a few pointers.
Common follow-ups
- What if the list must not be modified, even temporarily? Use a stack to store values, which takes O(n) extra space.
- How can recursion solve it? Recursively compare nodes from the ends, using O(n) call-stack space.
- What about empty or single-node lists? Both are palindromes; the code handles them directly.