FastPrep
Problem · Linked List

Find the Intersection Node of Two Linked Lists

Learn this problem
● EasyMicrosoft logoMicrosoftINTERNONSITE INTERVIEW
See Microsoft hiring insights

Problem statement

Two acyclic singly linked lists are stored in one node table. Node i points to node next[i]; a value of -1 means that the node has no successor. The integers headA and headB are the head-node indices, or -1 for an empty list.

Return the index of the first node that is reachable from both heads. Intersection is based on node identity, not equal values. Once the lists reach the same node, they share the remaining suffix. Return -1 if they do not intersect.

Function

findIntersectionNode(next: int[], headA: int, headB: int) → int

Examples

Example 1

next = [1,2,3,-1,2]headA = 0headB = 4return = 2

The first list follows 0 -> 1 -> 2 -> 3, while the second follows 4 -> 2 -> 3. Their first shared node is index 2.

Example 2

next = [1,-1,3,-1]headA = 0headB = 2return = -1

The two chains end separately, so there is no shared node.

Example 3

next = [1,2,-1]headA = 0headB = 0return = 0

Both lists start at the same node, so that head is the intersection.

Constraints

  • 0 <= next.length <= 200000
  • Every entry of next is -1 or a valid node index.
  • Each chain reachable from headA or headB is acyclic.
  • Each head is -1 or a valid node index.

More Microsoft problems

drafts saved locally
public int findIntersectionNode(int[] next, int headA, int headB) {
  // write your code here
}
next[1,2,3,-1,2]
headA0
headB4
expected2
checking account