Chain Reads the Same Backwards
Problem
Given the head of a singly linked list of digits, return True if the values read the same from front to back as from back to front. The list has between 1 and 100,000 nodes. Aim for O(n) time and O(1) extra memory, which rules out copying the values into a Python list, and leave the list in its original shape when you are done.
Examples
Input: 1 -> 2 -> 2 -> 1
Output: TrueInput: 1 -> 2
Output: FalseInput: 7
Output: True
Why: edge case, a single node is a palindromeHints
0 / 3
Comparing the first value with the last is easy in an array, but a singly linked list cannot walk backwards. What if the back half pointed the other way?
Move a slow pointer one step and a fast pointer two steps at a time. When fast runs out, slow is at the start of the back half.
Reverse the back half in place, walk it alongside the front half comparing values, then reverse it again to restore the list.
Solution
A palindrome check compares the i-th value from the front with the i-th value from the back, and the only obstacle is that the back of a singly linked list cannot be walked in reverse. Fast and slow pointers find the middle in one pass: when the fast pointer runs out, the slow one stands at the first node of the back half (the middle node itself, for an odd length). Reversing the list from there makes the back half readable from the last node inward, so two pointers can compare it with the front half. The comparison stops when the reversed half runs out, which also ignores a lone middle node. Reversing that half a second time puts every link back. Time is O(n) and extra space is O(1).
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def reverse(node):
prev = None
while node:
node.next, prev, node = prev, node, node.next
return prev
def is_palindrome(head):
slow = fast = head
while fast and fast.next: # slow ends at the back half
slow, fast = slow.next, fast.next.next
tail = reverse(slow)
left, right, same = head, tail, True
while right:
if left.val != right.val:
same = False
break
left, right = left.next, right.next
reverse(tail) # restore the original links
return same
print(is_palindrome(build([1, 2, 2, 1]))) # -> True
print(is_palindrome(build([1, 2]))) # -> False
print(is_palindrome(build([7]))) # -> True
chain = build([1, 2, 3, 2, 1])
print(is_palindrome(chain), dump(chain)) # -> True [1, 2, 3, 2, 1]Stuck on the idea rather than the code? Fast and Slow Pointers covers it.