Two singly linked lists a and b may merge: from some node onward they share the exact same tail. Find the value at the first shared node, or report that they never merge.
Because nodes can't be shared across two separately-built lists here, the merge is described structurally. You're given:
- a — list A's values, in order.
- b — list B's values, in order.
- skipA — the 0-based index in a where the shared tail begins, or -1 if the lists don't merge.
- skipB — the 0-based index in b where that same shared tail begins, or -1.
When they merge, a.slice(skipA) is identical to b.slice(skipB) (the shared suffix). Return the value at that first shared node — i.e. a[skipA]. If the lists don't merge, return null.
This is the classic "find the intersection node" interview problem in an array-encoded form; the optimal idea (align the two walkers by the length difference, then advance together) is the same.
Example
a[2..] = [8,4,5] equals b[3..] = [8,4,5]; the first shared value is 8.
Constraints
- The number of nodes in each list is in the range [0, 30000].
- 1 <= Node.val <= 100000
- skipA and skipB are valid indices into their lists, or both -1 when there is no intersection.
- When skipA, skipB >= 0, a.slice(skipA) deep-equals b.slice(skipB).
Intuition
Two lists intersect when, from some node on, they share the exact same tail. The brute-force check is the nested one: for every node in list A, walk all of list B looking for the same node (here, the same position in the shared suffix).
function getIntersectionValue(a, b, skipA, skipB) {
if (skipA < 0 || skipB < 0) return null; // no merge
// For each node in A, look for a matching shared-suffix node in B.
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < b.length; j++) {
// Same node iff both sit in the shared suffix at the same offset.
if (i >= skipA && j >= skipB && i - skipA === j - skipB) {
return a[i]; // first such match is the intersection
}
}
}
return null;
}The nested scan is O(m × n). Can we do better?
The key observation: if the lists merge, they share a common tail, so they have the same number of nodes after the intersection. The only thing in the way is that the two lists can have different lengths before the merge, so a node at distance d from head A isn't at distance d from head B.
The elegant fix is the length-alignment two-pointer walk: send pointer pa through A then B, and pb through B then A. Each covers m + n nodes total, so after the switch they're aligned and arrive at the first shared node on the same step (or both hit null together if there's no merge). No length pre-count, O(1) space.
Note on the model: this page is the array-encoded form of the classic node-identity problem (a node is (list, index), the same node when both lie in the shared suffix at the same offset). The encoding makes the first shared node's value simply a[skipA], so the stored solution returns that directly — but the alignment walk below is the idea you'd run on real shared nodes.
(Two lists sharing a tail aren't a single chain, so a node-chain diagram would misrepresent them — the alignment is shown as a trace instead.) Take A = 4 -> 1 -> 8 -> 4 -> 5 (length 5) and B = 5 -> 6 -> 1 -> 8 -> 4 -> 5 (length 6), sharing the tail 8 -> 4 -> 5:
- Step 0 —
paat A's head (4),pbat B's head (5). pa is 2 nodes before the shared8; pb is 3 before it. Misaligned by the length gap (6 − 5 = 1). - pa reaches A's end after 5 steps and switches to B's head. pb reaches B's end after 6 steps and switches to A's head. Each has now walked 5 + 6 = 11 nodes.
- From the switch,
pais 3 nodes into the combined walk's second leg andpbis 2 — and because each will walk the other list's prefix, the leftover distance to the shared8is now identical for both. - They meet on the same physical node — the first shared
8. That's the intersection. (Had the lists not merged, both would reachnullon the same step and we'd report no intersection.)
Optimization
Two-pointer length alignment
If the lists merge, they share a common tail, so their suffixes line up at the end. The only obstacle is that the two lists can have different lengths, so a node at distance d from one head isn't at distance d from the other.
The trick: let two walkers traverse a then b, and b then a. Each walker covers len(a) + len(b) nodes total, so after the switch they become aligned — they reach the first shared node at the same step. If there's no shared node, both reach the end (null) together. This needs no length precomputation and O(1) space.
Here the lists are array-encoded with an explicit skipA/skipB, so the "shared tail" is a.slice(skipA). We still drive the answer with the same alignment idea: advance both indices, and the first index pair where the remaining suffixes coincide is the intersection. With the given encoding that first coincidence is exactly a[skipA] when skipA >= 0, and null otherwise.
O(m + n) time, O(1) space.
function getIntersectionValue(a, b, skipA, skipB) {
// No merge point was supplied: the lists don't intersect.
if (skipA < 0 || skipB < 0) return null;
// The shared tail begins at index skipA in a; that node's value is the answer.
// (a.slice(skipA) is guaranteed identical to b.slice(skipB) by the encoding.)
return a[skipA] ?? null;
}Complexity analysis
Time complexity: O(m + n). Here's why:
- The alignment walk sends each pointer through both lists once — at most
m + nsteps before they meet or both reach the end. - The array-encoded form resolves the answer in O(1) from
skipA, but the underlying node-identity algorithm is the linear walk.
Either way there's no nested scan, so it's O(m + n) — versus the brute force's O(m × n).
Space complexity: O(1). Here's why:
- The alignment walk keeps only two pointers; nothing scales with the list sizes.
- A hash-set alternative (store all of A's nodes, scan B) would cost O(m) — the two-pointer walk avoids it.
So the optimal approach is O(1) auxiliary space.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| a = [2,6,4], b = [1,5], skipA = -1, skipB = -1 | null | No merge point supplied — the lists never intersect. |
| a = [1], b = [1], skipA = 0, skipB = 0 | 1 | Smallest intersection — both single-node lists share that node. |
| a = [4,1,8,4,5], b = [5,6,1,8,4,5], skipA = 2, skipB = 3 | 8 | Different lengths before the shared tail [8,4,5] — answer is the first shared value, 8. |
| a = [], b = [1,2,3], skipA = -1, skipB = -1 | null | Empty list A can't intersect anything. |
| a = [1,2,3,4,5], b = [99,4,5], skipA = 3, skipB = 1 | 4 | Shared tail [4,5] begins at index 3 in A and 1 in B. |
| a = [8,8,8], b = [8,8,8], skipA = 0, skipB = 0 | 8 | Identical lists that merge at the head — duplicate values don't fool the position-based identity. |
Try it yourself
Write your solution against the real judge before checking the reference.