Topics › Linked List › Medium Problems of LL

Find the intersection point of Y LL

Medium TUF ID 621 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Two singly linked lists start at headA and headB. They may merge: from some node onward both lists run through the very same node objects down to the common null, so on paper the picture looks like the letter Y. Return that first common node, or null if the lists never merge. Neither list has a cycle, and both lists must be left exactly as they were.

“Common” means the same object in memory. Two different nodes that happen to hold the same value are not an intersection, so every comparison in this problem is a reference comparison (a == b), never a value comparison.

Constraints: each list has up to 3 × 10^4 nodes. The follow-up asks for O(m + n) time and O(1) extra memory, where m and n are the two lengths.

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

Example 1

A = 4 -> 1 -> [8 -> 4 -> 5]
B = 5 -> 6 -> 1 -> [8 -> 4 -> 5]     // bracketed nodes are the same objects in both lists
answer = the node holding 8

The 1 in A and the 1 in B are different nodes, so the lists first touch at 8.

Example 2

A = 2 -> 6 -> 4
B = 1 -> 5
answer = null                         // the two lists end separately

Approach 1: Brute force, compare every pair of nodes

Intuition. A node has exactly one next pointer. So once the two lists share a node, they share every node after it as well; they can never split again. That means the intersection is simply the first node of A that appears anywhere in B. The most literal way to test “appears anywhere in B” is to walk all of B for each node of A.

Algorithm.

1. For every node a of list A, from the head onward:
2. Walk every node b of list B. If a == b, return a.
3. If no pair matched, return null.

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;                   // same object, not merely the same value
        }
    }
    return null;
}

Complexity. Time O(m × n): in the worst case (no intersection) every node of A is compared with every node of B. Space O(1).

With two lists of 3 × 10^4 nodes that is 9 × 10^8 comparisons, far too slow. The waste is obvious: we walk B again and again just to ask a membership question.

Approach 2: Better, remember the nodes of A in a hash set

Intuition. “Is this node somewhere in A?” is a set-membership question, and a hash set answers it in expected constant time. Walk A once and put every node into the set. Then walk B; the first node of B that is already in the set is the merge point, by the same “never split again” argument as before.

Algorithm.

1. Insert every node of A into a HashSet<ListNode>.
2. Walk B. Return the first node contained in the set.
3. Return null when B ends.

static ListNode hashing(ListNode headA, ListNode headB) {
    Set<ListNode> nodesOfA = new HashSet<>();      // ListNode has no equals(), so the set compares identity
    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) for the set.

Our ListNode does not override equals or hashCode, so the set falls back to Object identity, which is exactly the comparison we want. If a node class compared by value, two equal-valued but separate nodes would be confused and this method would give wrong answers.

The time is now optimal; what remains is the O(m) memory.

Approach 3: Optimal, skip the length difference

Intuition. Think about the shape of the Y. The shared tail is literally the same chain of nodes, so it has the same length c in both lists. Write m = a + c and n = b + c, where a and b are the lengths of the private parts. The difference m - n = a - b comes entirely from the private parts.

Now advance a pointer in the longer list by |m - n| nodes. Afterwards both pointers are exactly the same number of nodes away from the end. If we move them together one step at a time, they enter the shared tail at the same moment, so the first time they point to the same node is the merge point. If there is no shared tail, they reach null on the same step, and null == null ends the loop with the right answer.

Algorithm.

1. Count lenA and lenB.
2. Advance the pointer of the longer list until the remaining lengths are equal.
3. Move both pointers one step at a time while they differ.
4. Return the pointer (the merge node or null).

static ListNode lengthDifference(ListNode headA, ListNode headB) {
    int lenA = length(headA), lenB = length(headB);
    ListNode a = headA, b = headB;
    while (lenA > lenB) { a = a.next; lenA--; }     // at most one of these two loops runs
    while (lenB > lenA) { b = b.next; lenB--; }
    while (a != b) {                                // equal distance to the end from here on
        a = a.next;
        b = b.next;
    }
    return a;                                       // the shared node, or null if both ran off the end
}

The helper is a plain count:

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

Complexity. Time O(m + n): two counting passes and one joint pass. Space O(1): a few pointers and two integers.

Approach 4: Optimal, two pointers that switch lists

Intuition. The same alignment can be achieved without counting. Let pointer a walk A and, when it falls off the end, restart at the head of B. Let b walk B and restart at the head of A. Using the notation above, a reaches the merge node after walking a + c + b nodes (all of A, then the private part of B), and b reaches it after b + c + a nodes. Those are the same number, so the pointers arrive at the merge node on the same step. If the lists never merge, a walks m nodes, then n nodes, and b walks n then m; both hit null after the same number of steps and the loop stops with null.

In other words, each pointer pays for the other list’s length, which cancels the difference that Approach 3 measured explicitly.

Algorithm.

1. Set a = headA and b = headB.
2. While a != b: move a to a.next, or to headB if a is null; move b to b.next, or to headA if b is null.
3. Return a.

static ListNode optimal(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;           // after m + n steps both have walked the same distance
        b = (b == null) ? headA : b.next;
    }
    return a;
}

Dry run on Example 1. Private parts: A has 4, 1 and B has 5, 6, 1' (the prime marks B’s own 1); shared tail 8, 4, 5.

At step 2 the values look tempting but a is on the shared 8 while b is still on B’s private 1', so they differ. After the switch, both have the same distance left, and they meet exactly at 8.

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

Both optimal methods are fine in an interview. The counting version is easier to explain from first principles; the switching version is shorter and is the one most people remember.

Edge cases and pitfalls

• No intersection. All four methods return null. The two optimal versions do not need a special case because both pointers become null on the same step.
• Intersection at a head. If A has no private part, the merge node is headA itself. The length method skips the difference in B and then finds a == b immediately.
• Same list twice. If headA == headB, the answer is that head. The switching loop never runs.
• Empty lists. A null head is handled by every method and gives null.
• Comparing values instead of references. a.val == b.val is a bug: 1 -> 2 -> 3 and a separately built 1 -> 2 -> 3 share no node. The Java tests include exactly that case.
• Infinite loop in the switching version. It relies on the lists being acyclic so that both walks end at null. With a cycle the pointers might never agree.
• Modifying the lists. Tricks that reverse a list or mark nodes do work, but the problem asks for the lists to be unchanged. None of the methods here write to any node.

Related problems

• Find the intersection point of Y LL is the same problem in the A2Z sheet.
• Detect a loop in LL is another question where node identity, not value, is what matters.
• Find the starting point in LL also lines two pointers up so they meet at a structurally special node.
• Find Middle of Linked List is another two-pointer walk that reasons about distances to the end.