Find the shared node of two Java linked chains by identity

Last updated: 1 Oct 20264 min read

tutorial

Two singly linked chains intersect only when they reach the same Node object, not when their payload strings happen to match.

Align the remaining lengths

Count each acyclic chain once. Advance the cursor of the longer chain by the difference in lengths, then move both cursors together until their references are identical or both reach null. Shared nodes form a common suffix because one Node has only one next link.

A payload comparison can report a false intersection. Two dispatch records may carry the same identifier and still live in separate node objects. The second fixture makes that distinction visible.

Handle cycles separately

Length counting cannot terminate on a cycle. If the chains are not known to be acyclic, first use cycle-entry detection and define what intersection means for cyclic inputs. This lesson deliberately solves the simpler acyclic contract.

Intersection is an ownership warning before partitioning or merging by relinking nodes. If two roots share a tail, changing one root's links can change the other root's traversal.

Working program

public class SharedDispatchTail {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId, Node next) { this.dispatchId = dispatchId; this.next = next; }
    }
    static int length(Node head) {
        int count = 0;
        for (Node cursor = head; cursor != null; cursor = cursor.next) count++;
        return count;
    }
    static Node intersection(Node first, Node second) {
        int firstLength = length(first), secondLength = length(second);
        while (firstLength > secondLength) { first = first.next; firstLength--; }
        while (secondLength > firstLength) { second = second.next; secondLength--; }
        while (first != second) { first = first.next; second = second.next; }
        return first;
    }
    public static void main(String[] args) {
        Node shared = new Node("dispatch-47", new Node("ship-82", null));
        Node intake = new Node("load-15", shared);
        Node audit = new Node("verify-35", new Node("hold-20", shared));
        System.out.println(intersection(intake, audit).dispatchId);
        Node separate = new Node("dispatch-47", null);
        System.out.println(intersection(intake, separate) == null);
    }
}

Output

dispatch-47
true

Cost and ownership

Counting and alignment visit at most O(a+b) nodes and use O(1) extra references. No hash set is needed. The result is a borrowed Node reference; callers must not infer sole ownership from finding it.

Common Mistakes

Do not use value equality to detect structural intersection.
Do not run the length pass on an unverified cyclic chain.
Do not destructively merge roots that already share a suffix.