Symmetric Bead Strand
A jewellery maker designs bracelets in a web app. Each bead is stored as a node holding a color code, linked to the next bead on the strand. The app can only walk the strand forwards from the clasp.
Some customers want a symmetric bracelet: it looks the same whether you start reading from the clasp or from the other end. Before an order is accepted, the app checks the strand, and the device it runs on is short on memory, so it should not copy the strand.
Your task
Write isSymmetric(head). Return true if the sequence of values in the linked list reads the same forwards and backwards, otherwise false.
An empty strand and a single bead both count as symmetric. Aim for O(n) time and O(1) extra memory. You may change the links while you work.
isSymmetric(head: ListNode) → bool
Examples
head = [3, 7, 5, 7, 3]
true
Read from either end you get 3, 7, 5, 7, 3. The middle bead, 5, pairs with itself.
head = [3, 7, 7, 4]
false
The middle two beads match, but the ends are 3 and 4. Read backwards the strand is 4, 7, 7, 3, which is different.
Constraints
- 0 ≤ number of beads ≤ 10,000
- -1,000 ≤ color code ≤ 1,000
Start with brute force
Copy every color code into an array, then check it with two indexes moving in from both ends. Or push every value on a stack and compare while popping.
Both take O(n) time, which is fine, but they also need O(n) extra memory: a full copy of the strand. The task asks for O(1) extra memory, which means working on the links themselves.
Hints
0 of 4 shown- Hint 1
In an array you would compare the first value with the last, the second with the second-to-last, and so on. What stops you from doing that on this strand?
- Hint 2
You cannot walk backwards from the far end. But what if the second half of the strand pointed the other way? Then you could walk inwards from both ends at once.
- Hint 3
You need two tools you may already know: finding the middle with a slow and a fast pointer, and reversing a list in place.
- Hint 4
Find the middle with slow/fast pointers. Reverse the list from
slowonward. Now walk one pointer fromheadand one from the reversed half's head, comparing values, until the reversed half runs out. Any mismatch meansfalse.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The array check compares pairs from the outside in. A singly linked list cannot walk backwards, so make the second half walk backwards: reverse it in place, then compare from both ends.
Trace 3 → 7 → 5 → 7 → 3:
- Find the middle. slow/fast go 3/3, then 7/5, then 5/3. fast.next is null, so slow stops on 5.
- Reverse from 5 onward. The second half was
5 → 7 → 3and becomes3 → 7 → 5. The first half still runs3 → 7 → 5, because 7 still points to 5. - Compare: left 3 vs right 3, left 7 vs right 7, left 5 vs right 5. The reversed half ends. Every pair matched, so return
true.
Loop on right, the reversed half, not on left. For an odd length the middle node belongs to both halves and is compared with itself, which is harmless. In real code you would reverse the second half back afterwards so the caller gets the strand unchanged; it is the same reversal loop again.
function isSymmetric(head) {
// 1. find the middle
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. reverse the second half
let prev = null;
while (slow !== null) {
const next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// 3. walk inwards from both ends
let left = head, right = prev;
while (right !== null) {
if (left.val !== right.val) return false;
left = left.next;
right = right.next;
}
return true;
}def is_symmetric(head):
# 1. find the middle
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
# 2. reverse the second half
prev = None
while slow is not None:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
# 3. walk inwards from both ends
left, right = head, prev
while right is not None:
if left.val != right.val:
return False
left = left.next
right = right.next
return TrueRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.