Coding Interview PatternsIntersection of Two Linked Lists
EasyFast and Slow Pointers

Intersection of Two Linked Lists

Explanation & Solution

Practice Problem

Description

Given the heads of two singly linked lists headA and headB, return the value of the node at which the two lists intersect. If the two linked lists have no intersection, return null.

The parameter skipA indicates how many nodes to skip in list A before the intersection begins, and skipB indicates how many nodes to skip in list B. The shared suffix starting at those positions represents the intersection.

Input:headA = [4,1,8,4,5], headB = [5,6,1,8,4,5], skipA = 2, skipB = 3
0
4
1
1
2
8
3
4
4
5
0
5
1
6
2
1
3
8
4
4
5
5

Output: 8

Explanation: The two lists intersect at the node with value 8. List A has 2 nodes before the intersection, list B has 3 nodes before it.

Constraints

  • The number of nodes in list A is in the range [1, 3 * 10⁴]
  • The number of nodes in list B is in the range [1, 3 * 10⁴]
  • 1 <= Node.val <= 10⁵
  • 0 <= skipA < listA.length
  • 0 <= skipB < listB.length
  • The intersection is guaranteed to be valid when it exists

Approach

Fast and Slow Pointers pattern

1. Understanding the Problem

  • Two linked lists may share a common suffix (tail portion)
  • The intersection node is where they start sharing nodes
  • We need to find the value of that intersection node

2. The Classic Two-Pointer Approach

  • Initialize pointer pA at headA and pointer pB at headB
  • Traverse both lists simultaneously
  • When pA reaches the end of list A, redirect it to headB
  • When pB reaches the end of list B, redirect it to headA
  • Both pointers now travel the same total distance: lenA + lenB
  • If an intersection exists, they will meet at the intersection node
  • If no intersection, both will reach null at the same time

3. Why Does This Work?

  • Let list A have length a and list B have length b
  • Let the shared portion have length c
  • Pointer A travels: a + (b - c) steps to reach the intersection
  • Pointer B travels: b + (a - c) steps to reach the intersection
  • Since a + b - c = b + a - c, both arrive at the same time

4. Implementation Note

  • In this test format, skipA and skipB tell us where the intersection begins
  • The solution verifies the shared suffix and returns the intersection value

Key Insight

  • The two-pointer technique elegantly handles the length difference between lists
  • No need to calculate lengths explicitly — the pointer swap naturally aligns them
Time
O(m + n) where m and n are the lengths of the two lists
Space
O(1)only two pointer variables are used

Solution Code

Previous
Sort List
Next
Find the Duplicate Number