Skip to main content

Intersection of Two Chains

Every problem on this page hands you two starting points and a single way to move: follow one pointer forward. Once two such walks touch the same node they never separate again, because every node has only one "next". So the two paths always form a Y: two private prefixes and one shared tail.

41561845ABa = 2b = 3c = 3 (shared)intersectionsame node, not same valuea + c + b = b + c + aswap heads, meet here
Otto hauls both lists into the one node they share.

The answer is always the first node of that shared tail, and there are two ways to find it.

  • Set. Walk the first chain to its end and remember every node. Then walk the second chain; the first node you have already seen is the answer. Costs O(m + n) time and O(m) memory.
  • Two-pointer switch. Walk both chains at once. When a pointer falls off the end, restart it at the other chain's head. Both pointers then cover a + c + b nodes, so they reach the shared node on the same step. Costs O(m + n) time and O(1) memory.

What changes from problem to problem is only what counts as "next".

.parentno pointers160Linked Lists1650LCA III1257Common Region

The hub: .next​

Otto, your interviewer

160. Intersection of Two Linked Lists​

160

Intersection of Two Linked Lists

LeetCode
Easy

Brute Force

FIG. INTERSECTION OF TWO LINKED LISTS 2● INTERACTIVE
visualization loads as you reach it
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
while headA:
y = headB
while y:
if headA == y:
return headA
y = y.next
headA = headA.next
return None
top ↑

.parent instead of .next​

Otto, your interviewer

1650. Lowest Common Ancestor of a Binary Tree III​

1650

Lowest Common Ancestor of a Binary Tree III

LeetCode
Medium

Climb to Root, then DFS (Recursive)

FIG. LOWEST COMMON ANCESTOR III CLIMB THEN DFS● INTERACTIVE
visualization loads as you reach it
def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
root = p
while root.parent:
root = root.parent
 
def lowestCommonAncestor(node):
nonlocal lca
if not node:
return 0
left = lowestCommonAncestor(node.left) if node.left else 0
right = lowestCommonAncestor(node.right) if node.right else 0
found = left + right + int(node == p) + int(node == q)
if not lca and found == 2:
lca = node
return found
 
lca = None
lowestCommonAncestor(root)
return lca
top ↑

Build the pointers first​

Otto, your interviewer

1257. Smallest Common Region​

1257

Smallest Common Region

LeetCode
Medium

Ancestor Set

FIG. SMALLEST COMMON REGION ANCESTOR SET● INTERACTIVE
visualization loads as you reach it
class Solution:
def findSmallestRegion(self, regions: list[list[str]], region1: str, region2: str) -> str:
parents = {}
for parent, *child in regions:
for c in child:
parents[c] = parent
ancestors = set()
root = region1
while root:
ancestors.add(root)
root = parents.get(root, None)
while region2 not in ancestors:
region2 = parents.get(region2, None)
return region2
top ↑

The three problems side by side:

ProblemChain stepPointers given?Set spaceSwitch space
160 Intersection of Two Linked Liststhe hubnode.nextO(m)O(1)
1650 LCA of a Binary Tree IIIfrom 160node.parentO(h)ancestors of pO(1)
1257 Smallest Common Regionfrom 1650parents[x]invert the rows into a map firstO(r + h)the map plus ancestorsO(r)the map itself
On this page