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)intersection
Two lists that intersect share the tail c; only the prefixes a and b differ in length.

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".

The hub: .next​

Narrative

The plain version. Two singly linked lists that may share a tail, and the pointer to follow is .next.

All four solutions are here: brute force, the set, the length-difference alignment, and the two-pointer switch. The length-difference solution is the switch with its trick made explicit: measure both lengths, give the longer list a head start equal to the difference, then walk both together. The switch gets the same alignment for free by making each pointer walk both prefixes. Learn the None stop in the switch's explanation well, because the next two problems use it unchanged.

160. Intersection of Two Linked Lists​

4 Approaches
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

.parent instead of .next​

Narrative

160 on a tree. You get two tree nodes p and q, each with a .parent pointer, and no root.

Walking up from a node traces a linked list that ends at the root. Walking up from p and from q gives two lists that merge where the paths meet, and that merge point is their lowest common ancestor. Replace .next with .parent and the Ancestor Set and Two-Pointer Switch solutions are 160's set and switch. The first solution on this page climbs to the root and then counts; it is the Lowest Common Ancestor family's approach and is included so you can compare the two.

1650. Lowest Common Ancestor of a Binary Tree III​

Medium·
3 Approaches
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

Build the pointers first​

Narrative

1650 with no pointers given. The input is a list of rows, each one a region followed by the regions directly inside it. The problem never mentions a tree or a list.

Invert every row into parents[child] = parent and you have 1650 again, with parents[x] as the "next" step. Both solutions carry over: the ancestor set and the two-pointer switch. The one new step is building the map. The lesson is to recognize this family from the Y shape, even when the problem never names it.

1257. Smallest Common Region​

Medium·
2 Approaches
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

The three problems side by side:

ProblemTitleChain stepPointers given?Set spaceSwitch space
160the hubIntersection of Two Linked Listsnode.nextO(m)O(1)
1650from 160LCA of a Binary Tree IIInode.parentO(h)ancestors of pO(1)
1257from 1650Smallest Common Regionparents[x]invert the rows into a map firstO(r + h)the map plus ancestorsO(r)the map itself