Does the list read the same backwards
Check whether a list is a palindrome in one pass and with no extra memory, by reversing its second half. About 18 minutes.
Three tools in one
A palindrome list reads the same forwards and backwards, like 1, 2, 3, 2, 1. You can't walk a singly linked list backwards, so use what you know.
First, find the end of the first half with fast and slow pointers. Second, reverse everything after it. Now the second half runs from the old tail back towards the middle. Third, walk one pointer from the head and one from the new start of the second half, comparing values as you go.
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.nextFind the middle: slow stops on node 3. The second half after it is 2, 1.
The odd middle and the walk
With an odd number of nodes, the middle node stays out of the second half, which is fine: it has no partner, and any value matches itself. The loop above stops with slow on the middle (odd) or the first of the two middles (even), so reversing from slow.next works for both.
Compare while the reversed half has nodes. The first half may be one node longer, and that last node is skipped naturally. If any pair differs, answer false.
prev = None
cur = slow.next
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
a, b = head, prev
while b:
if a.val != b.val:
return False
a, b = a.next, b.next
return TrueA list has 5 nodes. Which node has no partner to compare with?
- AThe middle node, which matches itself
- BThe first node
- CThe last node
Show the answer
The middle node, which matches itself. In an odd-length list the middle is its own mirror image.
Palindrome list
Given the head of a singly linked list, return whether its values read the same from the front as from the back. Try to use only a few extra variables rather than copying the values.
head = [1, 2, 3, 2, 1] → true
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val ≤ 1,000,000