You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large-scale backend system maintains multiple data pipelines represented as linked lists. Sometimes, two different pipelines share a common tail due to data deduplication, shared processing stages, or reference reuse.
Each pipeline is represented as a singly linked list, and at some point, both lists may converge to the same node, after which all remaining nodes are shared.
The platform needs to detect whether two linked lists intersect and, if they do, identify the node where the intersection begins.
This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect.
If the two linked lists do not intersect, return null.
The intersection is defined by reference equality, not by node value.
Input Format
headA: head of the first singly linked listheadB: head of the second singly linked list
Each node is defined as:
ListNode { int val; ListNode next; }
Output Format
- Return the reference to the intersecting node
- Return
null if no intersection exists
Examples
Example 1:
Input: listA = [4,1,8,4,5]
listB = [5,6,1,8,4,5]
intersection node value = 8
Output: Node with value 8
Example 2:
Input: listA = [1,9,1,2,4]
listB = [3,2,4]
intersection node value = 2
Output: Node with value 2
Example 3:
Input: listA = [2,6,4]
listB = [1,5]
Output: null