Skip to main content

160. Intersection of Two Linked Lists

easy

Find the node where two singly linked lists merge. The two-pointer trick lets you align them in O(n + m) time and O(1) space — a satisfying elegant solve once you see it.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 have no intersection at all, return null. The lists must retain their original structure after the function returns.

Constraints

  • The number of nodes of listA is in the m.
  • The number of nodes of listB is in the n.
  • 1 <= m, n <= 3 * 10^4
  • 1 <= Node.val <= 10^5
  • 0 <= skipA < m, 0 <= skipB < n

Examples

Example 1

Input
intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output
Intersected at '8'

Explanation: From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5].

Example 2

Input
intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output
No intersection

Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Lists do not share any nodes.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash set of nodes in A; walk B and return the first node found in the set. O(n + m) time AND O(n) space.

Hint 2

For O(1) space: if both lists intersect, their tails are identical. The lengths can differ — align them.

Hint 3

Two pointers p1 = headA, p2 = headB. Walk together; when one hits null, redirect it to the OTHER head. After at most two passes they meet at the intersection (or both at null if no intersection).

Solution approach

Reveal approach

Two-pointer alignment. Initialize p1 = headA, p2 = headB. Loop: if p1 == p2 return p1 (covers both the intersection-found case and the both-null no-intersection case). Otherwise advance each pointer; when one reaches null, redirect it to the OPPOSITE list's head. After at most (lenA + lenB) steps the pointers either meet at the intersection node (because both pointers have traveled the same total distance — lenA + lenB) or both reach null simultaneously. O(n + m) time, O(1) extra space.

Complexity

Time
O(n + m)
Space
O(1)

Related patterns

  • linked-list
  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Intersection of Two Linked Lists and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →