Intersection of Two Linked Lists

Easy Problem 53 of 151 Java and Python

Problem

Given the heads of two singly linked lists headA and headB, return the node at which they intersect (the first node they share), or null if they never meet.

The lists have no cycles and must keep their original structure.

Example 1

Input: A = [4, 1, 8, 4, 5], B = [5, 6, 1, 8, 4, 5], sharing the tail 8 → 4 → 5
Output: the node with value 8
Why: The two 1s are different nodes; 8 is the first shared node.

Example 2

Input: A = [2, 6, 4], B = [1, 5], no shared nodes
Output: null

Constraints

1 ≤ m, n ≤ 3 × 10⁴
Follow-up: O(m + n) time and O(1) memory.

Explanation

If the lists had the same length before the shared part, walking both in step would hit the meeting node together. The problem is the different lengths.

Fix it by letting each pointer walk its own list and then the other one. Both then travel a + c + b steps (a, b = the unshared parts, c = the shared tail), so they arrive at the meeting node at the same moment, or both reach null if there is none.

Approach 1 · Naive

Hash set of list A

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

Store every node of A, then walk B and return the first node that is in the set.

Add all nodes of A to a set.
Walk B; return the first node found in the set, or null.

Java

import java.util.*;

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> seen = new HashSet<>();
        for (ListNode node = headA; node != null; node = node.next) {
            seen.add(node);
        }
        for (ListNode node = headB; node != null; node = node.next) {
            if (seen.contains(node)) {
                return node;
            }
        }
        return null;
    }
}

Python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        seen = set()
        while headA:
            seen.add(headA)
            headA = headA.next
        while headB:
            if headB in seen:
                return headB
            headB = headB.next
        return None

Approach 2 · Optimal

Switch heads

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

Two pointers walk their lists; when one reaches the end it restarts at the other list's head. They meet at the intersection or at null.

Set a = headA, b = headB.
While a != b: a = a == null ? headB : a.next; b = b == null ? headA : b.next.
Return a.

Java

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

Python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a, b = headA, headB
        while a is not b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

Complexity compared

Approach	Time	Space
Naive Hash set of list A	O(m + n)	O(m)
Optimal Switch heads	O(m + n)	O(1)

Key takeaways

Intersection is about the same node, not the same value.
The switch trick cannot loop forever: after at most m + n steps both pointers are null.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem