The challenge
Return the first shared node of two acyclic lists, or null if they do not intersect.
Intersection means the same node object, not matching values. Once lists intersect, their suffix is shared.
Example
A: 1 → 3 → 7 → 9; B: 2 → 7 → 9. Both refer to the same node 7.
Use the walkthrough below to inspect the input and each state change.
See Intersection, step by step
Follow the pointers. Watch each link change.
A1headAA1headBB1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 3 | A3 |
| A3 | 7 | A4 |
| A4 | 9 | null |
| B1 | 2 | A3 |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 3 (A2) → 7 (A3) → 9 (A4); B: 2 (B1); parameters: {"sharedAt":2}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Switching to the other head cancels the difference in prefix lengths.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def intersection(head_a, head_b):
a, b = head_a, head_b
while a is not b:
a = a.next if a else head_b
b = b.next if b else head_a
return a
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* intersection(Node* head_a, Node* head_b) {
Node* a = head_a;
Node* b = head_b;
while (a != b) {
a = a ? a->next : head_b;
b = b ? b->next : head_a;
}
return a;
}