Problem overview
The method getIntersectionNode receives the heads of two singly linked lists, headA and headB. The lists may merge into one shared tail. If they do, the method returns the first node that belongs to both lists. If they never meet, it returns null. Neither list may be changed, and there are no cycles.
In the first example, list A reads [4, 1, 8, 4, 5] and list B reads [5, 6, 1, 8, 4, 5]. The nodes holding 8, 4, 5 are the same three objects in both lists, so the answer is the node with value 8. Two nodes with the value 1 appear before it, but those are separate nodes, one in each list.
The important word is node. The method returns the shared node, not a value. Two different nodes can hold equal values without being an intersection, and the check must compare nodes themselves.
Approach: align the lists, then walk together
The brute-force way compares every node of A with every node of B, which costs O(m * n). A better way stores all nodes of A in a Set and walks B until it finds a node in the set. That is O(m + n) time but O(m) extra memory. The follow-up asks for O(m + n) time with O(1) memory, and this lesson delivers it.
Once two lists merge, they stay merged: everything after the intersection is shared, so the tail has the same length from both sides. That means the intersection is the same distance from the end in both lists. The only reason two pointers can't simply walk side by side is that the lists may start at different distances from the end. If A has 5 nodes and B has 6, B's pointer must skip its first node.
So the plan has three parts:
- Count the nodes in each list.
- Advance the pointer of the longer list by the difference in lengths.
- Move both pointers one node at a time until they refer to the same node.
After step 2 both pointers are the same distance from the end. If the lists intersect, the pointers reach the shared node on the same step. If they don't, both reach null on the same step, and null === null ends the loop with the right answer.
Try example 1 by hand. The lengths are 5 and 6, so B's pointer skips one node and starts at the node holding 6. Then both walk: A is at 4 and B at 6, then A at 1 and B at 1 (different nodes), then both reach the node holding 8, which is the same node. The loop stops there.
Step by step
- Compute both lengths with a helper called
size, writingsizeAandsizeBasconstvalues. The lesson uses the helper first and defines it afterwards. - Create the walking pointers
nAandnBwithlet, typedListNode | null. They will move, soconstwould not work. Using separate variables also keepsheadAandheadBuntouched. - Compare the lengths. If A is shorter, B is the longer list; otherwise A is at least as long.
- Skip the extra nodes of the longer list with a second helper,
moveNode, and assign the result back to the pointer. The helper can't change whatnBrefers to, since it only receives a copy of the reference. It returns the node where it stopped. In theelsebranch the difference may be 0, which moves nothing. - Loop while
nA !== nB. This compares references. For objects,!==asks whether both sides are the very same object, which is exactly the question being asked. - Advance both pointers by one node inside the loop.
- Return
nA. When the loop ends,nAandnBare equal: either both are the intersection node or both arenull. - Write
size. Start a counter at 0 and loop withwhile (head), which is true for any node and false fornull. Count each node and move tohead.next, then return the counter. - Write
moveNode. Whilekis positive, step tonode.nextand decreasek. Return the node you end on.
The solution in TypeScript
class Solution {
getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
const sizeA: number = this.size(headA);
const sizeB: number = this.size(headB);
let nA: ListNode | null = headA;
let nB: ListNode | null = headB;
if (sizeA < sizeB) {
nB = this.moveNode(nB, sizeB - sizeA);
} else {
nA = this.moveNode(nA, sizeA - sizeB);
}
while (nA !== nB) {
nA = nA!.next;
nB = nB!.next;
}
return nA;
}
size(head: ListNode | null): number {
let count: number = 0;
while (head) {
count++;
head = head.next;
}
return count;
}
moveNode(node: ListNode | null, k: number): ListNode | null {
while (k > 0) {
node = node!.next;
k--;
}
return node;
}
}
The TypeScript details worth knowing:
ListNode | null. A union type says a variable holds either a node ornull. The type ofnextis the same union. It documents that every walk along the list can end innull.- The non-null assertion
!.nA!.nexttells the compiler you knownAisn'tnullat that point. In strict mode the compiler would rejectnA.nextwithout it, becausenAmight benull. It is a promise, not a check. Types are erased when TypeScript compiles to JavaScript, so the!disappears and nothing is tested at run time. It is safe here because the pointers are aligned and reachnulltogether, so the loop stops before either isnull. - Parameters are copies of references. Reassigning
headinsizeornodeinmoveNodeonly moves that local variable. The caller's variables and the list itself are unchanged, which satisfies the requirement to keep the original structure. - Methods calling methods.
this.size(...)andthis.moveNode(...)need thethis.prefix. Without it, TypeScript looks for a function with that name outside the class. - Annotations on locals. Writing
const sizeA: numberis allowed but optional, because the compiler infers it from the return type. It does no harm and keeps the lesson's code explicit.
Complexity
Time: O(m + n). Counting walks each list once. Skipping walks part of the longer list, at most max(m, n) nodes. The final loop takes at most min(m, n) steps. All of these add up to a small multiple of m + n.
Space: O(1). The code uses two counters and two pointers. It builds no array, set or copy of the lists.
Edge cases and common mistakes
- No intersection. For
[2, 6, 4]and[1, 5], A is one node longer, so A's pointer skips its first node, then both pointers reachnulltogether and the method returnsnull. - Equal lengths. The difference is 0, so
moveNodereturns its argument unchanged. If the heads are the same node, the loop doesn't run and that head is returned. - Comparing values. Using
nA.val !== nB.valwould stop at the first equal values, even if they are in different nodes. Example 1 has two separate nodes holding 1, which would make this version stop at the wrong place. - Intersection at the last node. The pointers need to advance up to the end of the shorter list. The loop condition handles this without special code.
- Modifying the lists. Changing
nextpointers, for instance to mark visited nodes, would violate the rule that the structure must stay intact. - Forgetting to assign
moveNode's result. Callingthis.moveNode(nB, k)alone changes nothing, because the helper cannot move your variable. Always writenB = this.moveNode(...).
Testing
- A =
[4, 1, 8, 4, 5], B =[5, 6, 1, 8, 4, 5]sharing the tail from 8: the node with value 8. - A =
[1, 9, 1, 2, 4], B =[3, 2, 4]sharing the tail from 2: the node with value 2. - A =
[2, 6, 4], B =[1, 5], separate lists:null. - Two separate lists that both read
[8, 4]:null, even though the values match. - The same single list passed as both heads: that list's head.