Intersection Of Two Linked Lists · Interview Problem

Back to problems

Leetcode

Medium

Linked Lists

Two Pointers

Intersection Of Two Linked Lists

Find the first shared node between two singly linked lists, if one exists.

Acceptance 100%

Start Practice

Problem Statement

Given the heads of two singly linked lists, determine whether the two lists intersect by reference. If they do, return the node where the intersection begins. Otherwise, return null.

Two lists intersect when they share the same node object at some point onward, meaning the tail segment from that node is identical in both lists. Node values alone do not determine intersection.

Input Format

Two head nodes representing singly linked lists.
Each node contains a value and a next pointer.
The lists are finite and acyclic.

Output Format

Return the first shared node by reference.
If there is no shared node, return null.

Constraints

The lists are singly linked.
You may not modify the structure of either list.
Aim for $O(m+n)$ time and $O(1)$ extra space, where $m$ and $n$ are the lengths of the lists.

Examples

Sample cases returned by the problem API.

Example 1

Input

listA = 4 -> 1 -> 8 -> 4 -> 5
listB = 5 -> 6 -> 1 -> 8 -> 4 -> 5
(shared node starts at value 8)

Output

8 -> 4 -> 5

Explanation

Both lists point to the same node with value 8, so that node is the intersection start.

Example 2

Input

listA = 2 -> 6 -> 4
listB = 1 -> 5

Output

null

Explanation

The lists do not share any node by reference.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress