DSA-056 · Reverse a half, compare values, and restore links

Palindrome Linked List

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 21688 deterministic checks. Learner drafts are not executed.

Understand the problem

Return whether the values in an acyclic singly linked list read the same forward and backward. Use constant auxiliary workspace in the optimized method, and restore every original link before returning.

head is null or a finite acyclic chain of at most 100,000 nodes. Values are arbitrary final ints; equality compares int values here, unlike cycle and intersection problems.
Empty and singleton lists are palindromes. Return a boolean. Both methods leave the final head, identities, values, and every next reference exactly as before the call, on every normal return including false.
The optimized method temporarily reverses the second half, so it requires exclusive temporary mutation permission and a stable graph with no concurrent observers. The baseline is read-only and uses linear workspace. Restoration is a normal-return guarantee, not a guarantee against process termination or externally injected failures.

Examples

Input: N0(1)→N1(2)→N2(2)→N3(1)
Output: true; original links restored
Compare 1 with 1 and 2 with 2 after reversing N2→N3, then reverse back.
Input: N0(1)→N1(2)→N2(3)→N3(4)→N4(1)
Output: false; original links restored
The outside pair matches but the second pair 2/4 fails. The implementation records false and still restores.
Input: null
Output: true
No values violate the mirror condition and there are no links to restore.

Before you start

First-half tail from slow/fast traversal
Reversal invariant (DSA-049)
Distinguish temporary mutation from final restoration

Recognize the structure

Mirror comparison needs backward access, which a singly linked list lacks. Store values, recurse using O(L) stack, or temporarily reverse one half. The restoration requirement is part of correctness, so an early false return after mutation is incomplete.

Try before revealing

Hint 1

How can the end-to-middle values be made available in forward traversal?

Hint 2

Reverse just the second half and compare only as many pairs as that half contains.

Hint 3

Retain its reversed root, record mismatches, reverse back and reconnect before returning.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Store values, then compare mirrored indices

Collect boxed int values in an ArrayList and compare i with L−1−i using intValue, avoiding Integer reference equality. For [1,2,3,2,1], compare positions 0/4 and 1/3; the center need not be compared to another node. This takes O(L) time and O(L) storage without ever writing the input.

Improve the baseline

Find the first-half tail

Use middle=head and fast=head, moving while fast.next and fast.next.next exist. The second half has floor(L/2) nodes and excludes the center for odd lengths.

Compare against the reversed second half

Reverse middle.next and reconnect middle.next to the reversed head so the temporary chain is reachable. Walk left from head and right from reversed while right exists. Compare int values and retain a matches flag instead of returning early.

Restore through the saved reversed root

Traversal advances right to null, so keep the separate reversed reference. Reverse that chain again and assign middle.next to its restored head before returning matches.

Why it is correct

Pairs cover the condition

The reversed second-half node at position i has original index L−1−i. left has original index i for every comparison i<floor(L/2). Thus all required mirrored pairs are checked; an odd center imposes no additional condition.

The boolean is exact

matches starts true and changes only to false when a mirror pair differs. It is never reset to true. After the right half exhausts, it is true exactly when every required pair matched.

Restoration is complete

Reversing a finite acyclic chain twice restores every edge in that chain. Reconnecting middle.next restores the boundary edge too. First-half internal edges and all values were untouched. The restoration statement executes after both matching and mismatching comparisons, so every normal return satisfies the frame contract.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayList;

public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node(int value) { this.value = value; }
    }

    public static boolean isPalindrome(Node head) {
        if (head == null || head.next == null) return true;
        Node middle = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            middle = middle.next;
            fast = fast.next.next;
        }
        Node reversed = reverse(middle.next);
        middle.next = reversed;
        Node left = head, right = reversed;
        boolean matches = true;
        while (right != null) {
            if (left.value != right.value) matches = false;
            left = left.next;
            right = right.next;
        }
        middle.next = reverse(reversed);
        return matches;
    }

    private static Node reverse(Node head) {
        Node previous = null;
        while (head != null) {
            Node saved = head.next;
            head.next = previous;
            previous = head;
            head = saved;
        }
        return previous;
    }

    public static boolean baseline(Node head) {
        ArrayList<Integer> values = new ArrayList<>();
        for (Node p = head; p != null; p = p.next) values.add(p.value);
        for (int i = 0, j = values.size() - 1; i < j; i++, j--)
            if (values.get(i).intValue() != values.get(j).intValue()) return false;
        return true;
    }
}

Read the meaningful blocks

Keep the reversed head separately

reversed is the root used for restoration after right has moved to null. Restoring from right would restore nothing.

Record mismatches

The comparison loop does not return false immediately. Continuing is linear and makes the shared restoration path explicit.

Reconnect after reverse-back

middle.next=reverse(reversed) restores the second-half internal edges and its attachment; returning matches only follows this assignment.

Complexity

Optimized time O(L): midpoint, half reversal, comparison, and reverse-back are all linear passes. Auxiliary space is O(1), with no Node allocation. O(1) space does not imply the method is read-only during execution.

The value-array baseline is O(L) time and O(L) auxiliary storage. Recursive comparison also needs O(L) Java call frames and risks stack overflow on the declared large-input boundary.

Exact-state walkthroughs

Reveal normal and boundary traces

Even palindrome and full restoration

Input: [1,2,2,1] · Result: true

Step 1 of 11: Accept empty/singleton inputs without changing edges.

For longer lists the boolean will be returned only after restoration.

Palindrome — mirror comparisons and restored links

Phase: initial. middle: N0 · fast: N0 · reversed: null · left: null · right: null

All comparisons so far match: true. A false flag still proceeds to restoration.

N0: 1next → N1middlefast
N1: 2next → N2
N2: 2next → N3
N3: 1next → null

Cards remain in identity order; follow the named links for traversal order. Only second-half links change temporarily; every original edge must be restored before return.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":2,"next":"N3"},{"id":"N3","value":1,"next":null}]`
pointers	`{"middle":"N0","fast":"N0","reversed":null,"left":null,"right":null}`
matches	`true`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static boolean isPalindrome(Node head) {
11         if (head == null || head.next == null) return true;
12         Node middle = head, fast = head;
13         while (fast.next != null && fast.next.next != null) {
14             middle = middle.next;
15             fast = fast.next.next;
16         }
17         Node reversed = reverse(middle.next);
18         middle.next = reversed;
19         Node left = head, right = reversed;
20         boolean matches = true;
21         while (right != null) {
22             if (left.value != right.value) matches = false;
23             left = left.next;
24             right = right.next;
25         }
26         middle.next = reverse(reversed);
27         return matches;
28     }
29 
30     private static Node reverse(Node head) {
31         Node previous = null;
32         while (head != null) {
33             Node saved = head.next;
34             head.next = previous;
35             previous = head;
36             head = saved;
37         }
38         return previous;
39     }
40 
41     public static boolean baseline(Node head) {
42         ArrayList<Integer> values = new ArrayList<>();
43         for (Node p = head; p != null; p = p.next) values.add(p.value);
44         for (int i = 0, j = values.size() - 1; i < j; i++, j--)
45             if (values.get(i).intValue() != values.get(j).intValue()) return false;
46         return true;
47     }
48 }
49

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Accept empty/singleton inputs without changing edges.
For longer lists the boolean will be returned only after restoration.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":2,"next":"N3"},{"id":"N3","value":1,"next":null}]
pointers
{"middle":"N0","fast":"N0","reversed":null,"left":null,"right":null}
matches
true
phase
"initial"
Locate the tail of the first half.
The second half excludes the central node of an odd list.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":2,"next":"N3"},{"id":"N3","value":1,"next":null}]
pointers
{"middle":"N1","fast":"N2","reversed":null,"left":null,"right":null}
matches
true
phase
"middle"
Reverse one second-half edge with a saved successor.
The helper reverses only the chosen half. The caller retains its midpoint for reconnection.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":2,"next":null},{"id":"N3","value":1,"next":null}]
pointers
{"middle":"N1","fast":"N2","reversed":null,"left":null,"right":null}
matches
true
phase
"reverse"
helper
{"current":"N3","previous":"N2"}
Reverse one second-half edge with a saved successor.
The helper reverses only the chosen half. The caller retains its midpoint for reconnection.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":2,"next":null},{"id":"N3","value":1,"next":"N2"}]
pointers
{"middle":"N1","fast":"N2","reversed":null,"left":null,"right":null}
matches
true
phase
"reverse"
helper
{"current":null,"previous":"N3"}
Reconnect the reversed half and initialize mirror cursors.
right walks the original tail toward the center; left walks from head.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N3"},{"id":"N2","value":2,"next":null},{"id":"N3","value":1,"next":"N2"}]
pointers
{"middle":"N1","fast":"N2","reversed":"N3","left":"N0","right":"N3"}
matches
true
phase
"ready"
Compare a mirror pair and retain any mismatch.
No early return occurs: a false flag still proceeds to reverse-back.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N3"},{"id":"N2","value":2,"next":null},{"id":"N3","value":1,"next":"N2"}]
pointers
{"middle":"N1","fast":"N2","reversed":"N3","left":"N1","right":"N2"}
matches
true
phase
"compare"
pair
0
compared
["N0","N3"]
equal
true
Compare a mirror pair and retain any mismatch.
No early return occurs: a false flag still proceeds to reverse-back.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N3"},{"id":"N2","value":2,"next":null},{"id":"N3","value":1,"next":"N2"}]
pointers
{"middle":"N1","fast":"N2","reversed":"N3","left":"N3","right":null}
matches
true
phase
"compare"
pair
1
compared
["N1","N2"]
equal
true
Reverse the half back after comparisons.
This is the same reversal helper on the saved reversed root; original edges are recovered one by one.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N3"},{"id":"N2","value":2,"next":null},{"id":"N3","value":1,"next":null}]
pointers
{"middle":"N1","fast":"N2","reversed":"N3","left":"N3","right":null}
matches
true
phase
"restore"
helper
{"current":"N2","previous":"N3"}
Reverse the half back after comparisons.
This is the same reversal helper on the saved reversed root; original edges are recovered one by one.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N3"},{"id":"N2","value":2,"next":"N3"},{"id":"N3","value":1,"next":null}]
pointers
{"middle":"N1","fast":"N2","reversed":"N3","left":"N3","right":null}
matches
true
phase
"restore"
helper
{"current":null,"previous":"N2"}
Restore the original midpoint boundary before return.
Every original next field now equals its entry value, including after a mismatch.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":2,"next":"N3"},{"id":"N3","value":1,"next":null}]
pointers
{"middle":"N1","fast":"N2","reversed":"N3","left":"N3","right":null}
matches
true
phase
"restored"
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
true

Inner mismatch still restores

Input: [1,2,3,4,1] · Result: false

Step 1 of 12: Accept empty/singleton inputs without changing edges.

For longer lists the boolean will be returned only after restoration.

Palindrome — mirror comparisons and restored links

Phase: initial. middle: N0 · fast: N0 · reversed: null · left: null · right: null

All comparisons so far match: true. A false flag still proceeds to restoration.

N0: 1next → N1middlefast
N1: 2next → N2
N2: 3next → N3
N3: 4next → N4
N4: 1next → null

Cards remain in identity order; follow the named links for traversal order. Only second-half links change temporarily; every original edge must be restored before return.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":1,"next":null}]`
pointers	`{"middle":"N0","fast":"N0","reversed":null,"left":null,"right":null}`
matches	`true`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static boolean isPalindrome(Node head) {
11         if (head == null || head.next == null) return true;
12         Node middle = head, fast = head;
13         while (fast.next != null && fast.next.next != null) {
14             middle = middle.next;
15             fast = fast.next.next;
16         }
17         Node reversed = reverse(middle.next);
18         middle.next = reversed;
19         Node left = head, right = reversed;
20         boolean matches = true;
21         while (right != null) {
22             if (left.value != right.value) matches = false;
23             left = left.next;
24             right = right.next;
25         }
26         middle.next = reverse(reversed);
27         return matches;
28     }
29 
30     private static Node reverse(Node head) {
31         Node previous = null;
32         while (head != null) {
33             Node saved = head.next;
34             head.next = previous;
35             previous = head;
36             head = saved;
37         }
38         return previous;
39     }
40 
41     public static boolean baseline(Node head) {
42         ArrayList<Integer> values = new ArrayList<>();
43         for (Node p = head; p != null; p = p.next) values.add(p.value);
44         for (int i = 0, j = values.size() - 1; i < j; i++, j--)
45             if (values.get(i).intValue() != values.get(j).intValue()) return false;
46         return true;
47     }
48 }
49

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Accept empty/singleton inputs without changing edges.
For longer lists the boolean will be returned only after restoration.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":1,"next":null}]
pointers
{"middle":"N0","fast":"N0","reversed":null,"left":null,"right":null}
matches
true
phase
"initial"
Locate the tail of the first half.
The second half excludes the central node of an odd list.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":1,"next":null}]
pointers
{"middle":"N1","fast":"N2","reversed":null,"left":null,"right":null}
matches
true
phase
"middle"
Locate the tail of the first half.
The second half excludes the central node of an odd list.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":1,"next":null}]
pointers
{"middle":"N2","fast":"N4","reversed":null,"left":null,"right":null}
matches
true
phase
"middle"
Reverse one second-half edge with a saved successor.
The helper reverses only the chosen half. The caller retains its midpoint for reconnection.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":null},{"id":"N4","value":1,"next":null}]
pointers
{"middle":"N2","fast":"N4","reversed":null,"left":null,"right":null}
matches
true
phase
"reverse"
helper
{"current":"N4","previous":"N3"}
Reverse one second-half edge with a saved successor.
The helper reverses only the chosen half. The caller retains its midpoint for reconnection.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":null},{"id":"N4","value":1,"next":"N3"}]
pointers
{"middle":"N2","fast":"N4","reversed":null,"left":null,"right":null}
matches
true
phase
"reverse"
helper
{"current":null,"previous":"N4"}
Reconnect the reversed half and initialize mirror cursors.
right walks the original tail toward the center; left walks from head.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N4"},{"id":"N3","value":4,"next":null},{"id":"N4","value":1,"next":"N3"}]
pointers
{"middle":"N2","fast":"N4","reversed":"N4","left":"N0","right":"N4"}
matches
true
phase
"ready"
Compare a mirror pair and retain any mismatch.
No early return occurs: a false flag still proceeds to reverse-back.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N4"},{"id":"N3","value":4,"next":null},{"id":"N4","value":1,"next":"N3"}]
pointers
{"middle":"N2","fast":"N4","reversed":"N4","left":"N1","right":"N3"}
matches
true
phase
"compare"
pair
0
compared
["N0","N4"]
equal
true
Compare a mirror pair and retain any mismatch.
No early return occurs: a false flag still proceeds to reverse-back.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N4"},{"id":"N3","value":4,"next":null},{"id":"N4","value":1,"next":"N3"}]
pointers
{"middle":"N2","fast":"N4","reversed":"N4","left":"N2","right":null}
matches
false
phase
"compare"
pair
1
compared
["N1","N3"]
equal
false
Reverse the half back after comparisons.
This is the same reversal helper on the saved reversed root; original edges are recovered one by one.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N4"},{"id":"N3","value":4,"next":null},{"id":"N4","value":1,"next":null}]
pointers
{"middle":"N2","fast":"N4","reversed":"N4","left":"N2","right":null}
matches
false
phase
"restore"
helper
{"current":"N3","previous":"N4"}
Reverse the half back after comparisons.
This is the same reversal helper on the saved reversed root; original edges are recovered one by one.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N4"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":1,"next":null}]
pointers
{"middle":"N2","fast":"N4","reversed":"N4","left":"N2","right":null}
matches
false
phase
"restore"
helper
{"current":null,"previous":"N3"}
Restore the original midpoint boundary before return.
Every original next field now equals its entry value, including after a mismatch.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":1,"next":null}]
pointers
{"middle":"N2","fast":"N4","reversed":"N4","left":"N2","right":null}
matches
false
phase
"restored"
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
false

Empty list is a palindrome

Input: [] · Result: true

Step 1 of 2: Accept empty/singleton inputs without changing edges.

For longer lists the boolean will be returned only after restoration.

Palindrome — mirror comparisons and restored links

Phase: initial. middle: null · fast: null · reversed: null · left: null · right: null

All comparisons so far match: true. A false flag still proceeds to restoration.

No nodes at this step.

Cards remain in identity order; follow the named links for traversal order. Only second-half links change temporarily; every original edge must be restored before return.

State after this step
Variable	Value
nodes	`[]`
pointers	`{"middle":null,"fast":null,"reversed":null,"left":null,"right":null}`
matches	`true`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static boolean isPalindrome(Node head) {
11         if (head == null || head.next == null) return true;
12         Node middle = head, fast = head;
13         while (fast.next != null && fast.next.next != null) {
14             middle = middle.next;
15             fast = fast.next.next;
16         }
17         Node reversed = reverse(middle.next);
18         middle.next = reversed;
19         Node left = head, right = reversed;
20         boolean matches = true;
21         while (right != null) {
22             if (left.value != right.value) matches = false;
23             left = left.next;
24             right = right.next;
25         }
26         middle.next = reverse(reversed);
27         return matches;
28     }
29 
30     private static Node reverse(Node head) {
31         Node previous = null;
32         while (head != null) {
33             Node saved = head.next;
34             head.next = previous;
35             previous = head;
36             head = saved;
37         }
38         return previous;
39     }
40 
41     public static boolean baseline(Node head) {
42         ArrayList<Integer> values = new ArrayList<>();
43         for (Node p = head; p != null; p = p.next) values.add(p.value);
44         for (int i = 0, j = values.size() - 1; i < j; i++, j--)
45             if (values.get(i).intValue() != values.get(j).intValue()) return false;
46         return true;
47     }
48 }
49

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Accept empty/singleton inputs without changing edges.
For longer lists the boolean will be returned only after restoration.
nodes
[]
pointers
{"middle":null,"fast":null,"reversed":null,"left":null,"right":null}
matches
true
phase
"initial"
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
true

Test the contract

Input: null and singleton
Output: true; unchanged
Small inputs.
Input: [1,2,2,1]
Output: true; all edges restored
Even length.
Input: [1,2,3,2,1]
Output: true; all edges restored
Odd center skipped.
Input: [1,2,3,4,1]
Output: false; all edges restored
Mismatch near center.
Input: [MIN,MAX,MIN]
Output: true; unchanged
Full int equality, no boxing identity assumption.

Common mistakes and counterexamples

Return false as soon as a pair differs

Counterexample: [1,2,3,4,1] leaves a reversed tail if the function exits at 2 versus 4.

Retain a boolean and execute the common reverse-back step.

Restore from the exhausted right pointer

Counterexample: After comparison right==null, reverse(right) restores no original links.

Keep reversed as a separate unchanged root.

Compare Integer objects with == in the baseline

Counterexample: Values outside the small boxing cache can have distinct wrappers despite equal ints.

Unbox explicitly; the implementation uses intValue comparisons.

Check only the boolean in tests

Counterexample: A destructive palindrome implementation can return true while permanently changing the chain.

Snapshot exact next references, check them on true and false, then call again to expose hidden mutation.

Follow-ups

The list is strictly read-only.

Use the value-array baseline or another O(L)-memory structure. The constant-space reversal method is unsuitable even if it restores afterward, because concurrent observers could see intermediate edges.

Return the first mismatch positions.

Track pair index i and total length or derive its mirror index L−1−i. Preserve the restoration path before returning the result record.

Allow one deletion to make a palindrome.

After a first mismatch, two candidate omissions must be checked. A value array makes those checks straightforward; extending the restoring pointer method requires a new correctness argument and careful mutation boundaries.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 127/20,000 characters

Self-review

I know exactly which mirrored pair each comparison represents.I preserve the reversed root even as the comparison cursor advances.I verify every original edge after both outcomes and repeated calls.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.