Intersection of Two Linked Lists

Intersection of Two Linked Lists

1. What is this problem about?

The Intersection of Two Linked Lists interview question asks you to find the node at which two singly linked lists merge. If the two lists have no common intersection point, return null. The lists are guaranteed to have no cycles, and you must return the original node itself, not just its value.

2. Why is this asked in interviews?

Companies like Microsoft, Meta, and Adobe use this to test a candidate's mastery of Pointer Manipulation. It evaluations whether you can synchronize two pointers moving at different speeds or starting from different distances. It’s a classic Linked List interview pattern that rewards mathematical observation over complex algorithms.

3. Algorithmic pattern used

The most elegant solution uses the Two Pointers (Switching Heads) pattern.

1. Pointers: Initialize pA at the head of List A and pB at the head of List B.
2. Traversal: Move both pointers forward one step at a time.
3. The Switch: When pA reaches the end of List A, redirect it to the head of List B. When pB reaches the end of List B, redirect it to the head of List A.
4. Meeting Point: Because both pointers will eventually travel exactly length(A) + length(B) steps, they are guaranteed to meet at the intersection point or both reach null simultaneously.

4. Example explanation

List A: [a1, a2, c1, c2, c3], List B: [b1, b2, b3, c1, c2, c3].

• List A has length 5, List B has length 6.
• Pointer A travels: a1, a2, c1, c2, c3, null, b1, b2, b3, c1. (10 steps)
• Pointer B travels: b1, b2, b3, c1, c2, c3, null, a1, a2, c1. (10 steps)
• They both arrive at c1 at exactly the same time.

5. Common mistakes candidates make

• Difference in Length: Using a nested loop ($O(N \cdot M)$) to compare every node of A with every node of B.
• Hashing Overhead: Using a Hash Set to store nodes of A and checking B against it. While $O(N+M)$, it uses $O(N)$ extra space, whereas the two-pointer approach uses $O(1)$.
• Value vs. Node: Comparing node values instead of node references. Two different nodes might have the same value but represent different points in memory.

6. Interview preparation tip

The "Switching Heads" trick is a beautiful way to equalize distances. It’s a recurring theme in Two Pointers interview patterns where you need to coordinate two independent sequences.