☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Find the intersection point of Y LL

Medium TUF ID 2846 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the heads of two singly linked lists, headA and headB. The two lists may share a common tail: from some node onward, both lists consist of the very same node objects, which gives the picture its “Y” shape. Return the first shared node (the intersection point), or null if the lists never meet. The lists have no cycles and must be left unchanged.

Intersection is about node identity, not values. Two lists 1 -> 2 -> 3 and 1 -> 2 -> 3 built from different nodes do not intersect even though every value matches.

Constraints: 1 ≤ m, n ≤ 3 × 10^4 nodes in the two lists, values fit in a 32-bit signed integer. The follow-up asks for O(m + n) time and O(1) memory.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

A = 4 -> 1 -> 8 -> 4 -> 5
B = 5 -> 6 -> 1 -> 8 -> 4 -> 5        // the nodes 8 -> 4 -> 5 are shared
answer = the node holding 8

Example 2

A = 1 -> 9 -> 1 -> 2 -> 4
B = 3 -> 2 -> 4                        // the nodes 2 -> 4 are shared
answer = the node holding 2

Example 3

A = 2 -> 6 -> 4
B = 1 -> 5                             // no shared node
answer = null

Approach 1: Brute force, compare every pair

Intuition. The first node of A that also appears somewhere in B is the intersection, because everything after a shared node is shared too. So for each node of A, scan all of B looking for the same object.

Algorithm.

  1. For each node a of list A:
  2. For each node b of list B: if a == b, return a.
  3. Return null if no pair matched.
static ListNode bruteForce(ListNode headA, ListNode headB) {
    for (ListNode a = headA; a != null; a = a.next) {
        for (ListNode b = headB; b != null; b = b.next) {
            if (a == b) return a;              // identity, not value
        }
    }
    return null;
}

Complexity. Time O(m × n): every pair of nodes may be compared. Space O(1).

Correct, but quadratic. The Java test runs it on lists of 5 000 and 3 000 nodes (15 million comparisons), which is fine for a test but not for the stated limits.

Approach 2: Better, hash set of one list’s nodes

Intuition. Checking “is this node somewhere in A” is a membership question, and a hash set answers membership in constant time. Store every node of A, then walk B and return the first node found in the set.

Algorithm.

  1. Add every node of A to a HashSet<ListNode>.
  2. Walk B; the first node contained in the set is the answer.
  3. Return null if B ends.
static ListNode better(ListNode headA, ListNode headB) {
    Set<ListNode> nodesOfA = new HashSet<>();
    for (ListNode a = headA; a != null; a = a.next) nodesOfA.add(a);
    for (ListNode b = headB; b != null; b = b.next) {
        if (nodesOfA.contains(b)) return b;
    }
    return null;
}

Complexity. Time O(m + n): one pass over each list with O(1) average set operations. Space O(m): the set holds all nodes of A.

Since ListNode does not override equals and hashCode, the set compares nodes by identity, which is exactly the semantics we need. The remaining goal is to drop the extra memory.

Approach 3: Optimal, align by length difference

Intuition. If both lists had the same length, walking them in lock-step would reach the shared node at the same moment, because the shared tail has the same length in both. When the lengths differ, the longer list has extra nodes before the intersection (the shared tail is identical, so the difference must be in the private prefixes). Skip that many nodes in the longer list first, and then lock-step walking works.

Algorithm.

  1. Compute lenA and lenB.
  2. Advance a pointer in the longer list by |lenA - lenB| nodes.
  3. Move both pointers one node at a time until they are the same object (or both null).
  4. Return the pointer.
static ListNode optimalLengthDifference(ListNode headA, ListNode headB) {
    int lenA = length(headA), lenB = length(headB);
    ListNode a = headA, b = headB;
    for (int i = 0; i < lenA - lenB; i++) a = a.next;    // only one of these two loops actually runs
    for (int i = 0; i < lenB - lenA; i++) b = b.next;
    while (a != b) {                                     // both now have the same number of nodes left
        a = a.next;
        b = b.next;
    }
    return a;                                            // the meeting node, or null when both ran off the end
}

The length helper is a plain count:

static int length(ListNode head) {
    int n = 0;
    for (ListNode t = head; t != null; t = t.next) n++;
    return n;
}

Complexity. Time O(m + n): two counting passes plus one aligned pass. Space O(1).

When there is no intersection, both pointers have the same number of nodes left after alignment, so they become null in the same step; a != b is then false and the method returns null without any special case.

Approach 4: Optimal, two pointers that switch lists

Intuition. Here is a way to equalise the lengths without counting. Let pointer a walk list A and, when it falls off the end, continue from the head of B. Let b do the mirror image: walk B, then continue from the head of A. By the time a enters its second list it has walked m nodes, and when b enters its second list it has walked n nodes. After that, a has n nodes to go and b has m nodes to go, both of which end at the same null, so the two pointers are now aligned with respect to the shared tail and meet at the intersection. If there is none, they both reach null after exactly m + n steps and the loop exits with a == b == null.

Algorithm.

  1. Set a = headA, b = headB.
  2. While a != b: set a to headB if a is null, else a.next; set b to headA if b is null, else b.next.
  3. Return a.
static ListNode optimalTwoPointer(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;    // when a list ends, jump to the head of the other one
        b = (b == null) ? headA : b.next;
    }
    return a;                                // the intersection, or null when both are null together
}

Dry run on Example 2 (A = 1 9 1 2 4, B = 3 2 4, shared 2 4):

step a b
0 1 3
1 9 2
2 1 4
3 2 null
4 4 1 (restarted on A)
5 null 9
6 3 (restarted on B) 1
7 2 2, same node, stop

Complexity. Time O(m + n): each pointer walks at most m + n nodes. Space O(1).

All four methods are tested on the same Y shapes and must return the identical node object, both with the lists in the given order and with A and B swapped.

Edge cases and pitfalls