Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Walk both lists in lockstep. At each step, if either list has ended or the current values differ, return 0 (not equal). If both pointers reach null together, every value matched and the lengths are equal — return 1. O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you compare both values AND lengths — many candidates check values but forget that a prefix match with differing lengths is not equality.
Where candidates slip
Looping while only one pointer is non-null, or returning 1 after the loop without confirming both pointers reached null (so [1,2] vs [1,2,3] wrongly passes).
How to stand out
State the two failure modes up front (value mismatch, length mismatch), compare by value not identity, and confirm both pointers are null at the end.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCompare two linked listsvalues differ?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Lockstep Traversal — Walk Both Together (Optimal)
1Hint 1Explore hintHide hint
If you stepped through both lists at the same pace, what's the first thing that tells you they're different?
2Hint 2Explore hintHide hint
There are two ways to fail: the values at some position disagree, or one list ends before the other. The loop body catches the first — what catches the second?
3Hint 3Explore hintHide hint
When the loop stops, what must be true about both pointers for the lists to be identical?
A · Core idea
We walk the two lists side by side, failing fast on any value disagreement and checking lengths when the walk ends.
The loop guards both lists. We iterate while both a and b are non-null. Inside, if a.val != b.val the lists differ at this position → return 0 immediately. Otherwise advance both pointers. Using && (both non-null) means the loop stops as soon as the shorter list ends — we then inspect why.
Why values, not identity. The lists are separate objects; 'identical' means the same sequence of values, not the same physical nodes. So we compare a.val == b.val. Comparing references would return 0 for two independently built but value-equal lists — wrong for this problem.
The length check after the loop — the trap. When the loop exits, at least one pointer is null. The lists are identical only if both are null (they ended together). If one is still non-null, that list is longer, so return 0. This is the step candidates forget: [1, 2] vs [1, 2, 3] passes every value comparison, then the loop exits with a == null but b != null — the final check rejects it.
Why empty lists work. Two empty lists skip the loop entirely; both pointers are null, so the final check returns 1. An empty vs non-empty pair also skips the loop, but one pointer is non-null → 0.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
A = [1, 2], B = [1, 2, 3]Array state
pos 0
1 == 1 → advance
0C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Equality has two independent failure modes — content and length — and a single lockstep pass tests both: the loop body for content, the post-loop null check for length. Forgetting the length check is the classic bug. It's the same index-by-index comparison you'd write for two arrays.
ComplexityO(n) time, O(1) space — We advance both pointers once per node until a mismatch or the end → at most min(n, m) + 1 steps → O(n). Only two pointers → O(1) space.
E · Edge cases and pitfalls7A = [], B = [] — Loop never runs; both null → return 1.Explore edge casesHide edge cases
Edge cases handled
A = [], B = []Loop never runs; both null → return 1.A = [], B = [1]Loop skipped (a null); a is null but b is not → return 0.A = [5], B = [5]One match, both advance to null → return 1.
Pitfalls
- Returning 1 after the loop without confirming both pointers are null — a prefix match with unequal lengths wrongly passes.
- Looping with || (either non-null) instead of && — dereferences the null pointer of the shorter list.
- Comparing node identity instead of values — two value-equal but separate lists wrongly return 0.
- Advancing only one pointer, drifting the comparison out of alignment.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Missing the length check
If you return 1 right after the loop, [1, 2] vs [1, 2, 3] passes: both values match, the loop exits when A ends, and you never notice B has a leftover node. You must confirm both pointers are null.
Explore the code comparisonHide the code comparison
Missing the length check
If you return 1 right after the loop, [1, 2] vs [1, 2, 3] passes: both values match, the loop exits when A ends, and you never notice B has a leftover node. You must confirm both pointers are null.
Don't write this
while (a != null && b != null) {
if (a.val != b.val) return 0;
a = a.next; b = b.next;
}
return 1; // ignores that one list may be longerWrite this instead
while (a != null && b != null) {
if (a.val != b.val) return 0;
a = a.next; b = b.next;
}
return (a == null && b == null) ? 1 : 0;2Wrong loop connective
Looping while a != null OR b != null keeps going after the shorter list ends, so the next a.val (or b.val) dereferences null and crashes.
Explore the code comparisonHide the code comparison
Wrong loop connective
Looping while a != null OR b != null keeps going after the shorter list ends, so the next a.val (or b.val) dereferences null and crashes.
Don't write this
while a is not None or b is not None: # one may be None
if a.val != b.val: # AttributeError on None
return 0
a = a.next; b = b.nextWrite this instead
while a is not None and b is not None:
if a.val != b.val:
return 0
a = a.next; b = b.nextRevise
Carry the pattern into the interview
Pattern to remember
Lockstep traversal: advance both, fail on mismatch or length difference
Code pattern to memorize
while a and b:
if a.val != b.val: return 0
a, b = a.next, b.next
return 1 if a is None and b is None else 0Rules to remember
- 1Loop while both are non-null; the moment one ends, lengths differ unless the other also ended.
- 2Compare values here (
a.val != b.val), not node identity — two separate lists with equal values are 'identical'. - 3After the loop, return 1 only if both pointers are null — otherwise one list was longer.
- 4Advance both pointers every iteration so they stay aligned by index.
- 5Two empty lists are equal → return 1 (the loop never runs and both are null).
Use this pattern when
- Check if two singly linked lists have the same length and the same values in order
- Equality test as a building block (e.g. confirming a reversal or a copy)
- Comparing sequences where random access isn't available
- Validating that two list-building routines produced the same output
Choose another pattern when
- You need to know *where* they first differ, not just yes/no → return the index instead of a flag
- Order doesn't matter, only the multiset of values → sort or count, don't compare in place
- You're testing structural sharing (same nodes) → compare identity, this problem compares values
- Lists are huge and you only need a quick reject → compare lengths first as a cheap pre-check
Interview takeaway
List equality is a lockstep walk with two failure modes: a value mismatch, or a length mismatch (one ends before the other). Handle both and the rest is a clean linear scan — the same shape as comparing two arrays index by index.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternLockstep two-pointer comparison with explicit length handling: walk both lists together, fail on a value mismatch, and require both to end together. The same index-by-index equality check used for arrays and the backbone of palindrome verification.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Palindrome Linked ListCompare the list against its reversed second half — the same value-by-value lockstep check.
- Merge Two Sorted Linked ListsAlso a two-pointer walk over two lists, but interleaving by value instead of comparing for equality.
- Add Two NumbersWalk two lists in lockstep, but combine digits with a carry instead of comparing them.