Intersection of Two Linked Lists

The problem expects us to walk through two linked lists, that may possibly share a common node, and if they do, return that point of intersection.

The brute force approach will be taking one node of ListA at a time and matching it against every node of ListB. Nothing wrong with the approach except for the traversal cost. That part’s expensive.

Finding a cheaper way to do this matching, my first instinct said I should start copying all the nodes of ListA in a hashmap so that when traversing ListB we can access the nodes in constant time. Why a hashmap? Because the last problem I solved was a hashmap. Pardon my lazy instincts.

Okay, but what would the map even look like?? My first thought? Something like Map<number, ListNode>. Store the node's value as the key and the node itself as the value. Then, while traversing List B, take its value, look it up, and return the associated node.

Except that immediately falls apart the moment you find duplicate values on different nodes in the same linked list, which will silently replace the previous node link at the time of insertion. Bad idea.

What else? Wait. Unlike plan JS objects that notoriously ‘stringifies’ the keys, a Map can use anything as its key (Even, NaN, did you know?). So it can definitely store the node object references as keys like Map<ListNode, boolean>. Then, while traversing List B, I can ask whether that exact node reference already exists in the map.

That works.

But wait a sec-.

What do we even need the boolean for? It's doing absolutely nothing. Come to think of it, I don't even need to associate some information with each node. I only need to answer one question: Have I seen this exact node before?

That's not really a mapping problem anymore. It's a membership problem.

And I think Set<ListNode> would fit way better on this one than a Map. Traverse List A and add every node reference to the set. Then traverse List B. The first node already present in the set is the intersection.

Reminder to self: When the goal is association, and you want to attach some information with a key, can be a count, an index, another object, or whatever, reach for a map. But when the key itself is all you care about, and the only question is “have I seen this before?”, reach for a set. Always.

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    const store = new Set<ListNode>();

    // Inserting ListA in set
    while (headA) {
        store.add(headA);
        headA = headA.next;
    }

    // The Lookup
    while (headB) {
        if (store.has(headB)) return headB;
        headB = headB.next;
    }

    return null;
};

O(m + n) time, and O(n) space as you store List A. Pretty acceptable.