Workspace

Problem workspace

3 day streakD

Intersection of Two Linked Lists

EasyLinked ListsFast & slow pointers

The challenge

Return the first shared node of two acyclic lists, or null if they do not intersect.

Intersection means the same node object, not matching values. Once lists intersect, their suffix is shared.

Example

A: 1 → 3 → 7 → 9; B: 2 → 7 → 9. Both refer to the same node 7.

Use the walkthrough below to inspect the input and each state change.

See Intersection, step by step

Follow the pointers. Watch each link change.

5 nodes · singly linkedIDs = node identity · ∅ = null
Shared suffix: Read the inputIDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links. Node positions stay fixed while arrows change. The pointer strip and node table below give the same state in text.head · headA1A13A27A39A4∅headB2B1
CurrentResultYellow arrow: changed next link
headA1headAA1headBB1
Inspect node links
Each row is a distinct node object. D is the dummy sentinel.
NodeValueNext
A11A2
A23A3
A37A4
A49null
B12A3
Step 01 / 8

Read the input

IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.

Start from the input head pointers.
View original input

A: 1 (A1) → 3 (A2) → 7 (A3) → 9 (A4); B: 2 (B1); parameters: {"sharedAt":2}

Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.

Put it into code

Switching to the other head cancels the difference in prefix lengths.

Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def intersection(head_a, head_b):
    a, b = head_a, head_b
    while a is not b:
        a = a.next if a else head_b
        b = b.next if b else head_a
    return a

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap