Find the node where two lists join: walk each list, switch to the other head at the end, and both runners meet at the join.
▼The problem
LeetCode 160 (Easy). Given the heads of two singly linked lists, return the node where they intersect (the same node object, not just an equal value), or null if they never join.
Examples (LeetCode's): listA = [4,1,8,4,5], listB = [5,6,1,8,4,5] meet at the node with value 8 (both lists hold a 1, but those are two different nodes); listA = [2,6,4], listB = [1,5] → null.
The solution
def get_intersection_node(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 aTranscript
Intersection of Two Linked Lists. Given the heads of two linked lists, return the node where they join: the same node, not just an equal value. If they never join, return null.
List A is four, one, eight, four, five, and B is five, six, one, eight, four, five. Both hold a one, but those are different nodes. They first share the eight. In the second, the lists never join: null.
The slow way: for each node of A, scan all of B. With m and n nodes, that's m times n checks. A hash set of A's nodes is faster, but costs m extra space.
The key idea: two pointers that switch heads. Pointer A walks list A, then jumps to the head of B. Pointer B does the reverse. If A has a nodes of its own, B has b, and they share c, each pointer walks a plus c plus b. So they arrive at the join on the same step.
In code, start a pointer at each head. While they differ, step both forward, and send one that falls off the end to the other head. Return where they meet.
On the example, pointer A passes four, one, eight, four, five, then switches. Pointer B passes six nodes, then switches. After nine steps, both land on the eight. On the second, both reach null together.
That's at most m plus n steps each, O of m plus n time, and two pointers: O of one space.
Walk your list, switch heads, meet up. That's Intersection of Two Linked Lists.