Intersection Point of Two Linked Lists

1. Defining the Problem: What is an Intersection?

When we say two linked lists intersect, we don't just mean they contain nodes with the same value. We mean that at some point, they start sharing the exact same node objects, forming a 'Y' shape. From the intersection point onwards, the rest of the list is identical for both.

If the lists do not intersect at all, your function should return null.

2. Approach 1: The Hashing Method

As with many problems, a good first step in an interview is to find a working solution, even if it's not the most optimal one. A straightforward approach here involves using extra memory.

The idea is simple:

1. Traverse the first linked list (say, List A).
2. Store each node you visit in a HashSet. A HashSet is a good choice here because it provides average $O(1)$ time complexity for insertion and lookup.
3. Traverse the second linked list (List B). For each node, check if it already exists in the HashSet.
4. The very first node from List B that you find in the set is the intersection point. If you reach the end of List B without finding any, there is no intersection.

This video from 'take U forward' explains this hashing approach clearly.

Complexity Analysis

• Time Complexity: $O(N_1+N_2)$, where $N_1$ and $N_2$ are the lengths of the two lists. You traverse each list once.
• Space Complexity: $O(N_1)$ (or $O(N_2)$ if you store the second list). This is because you need to store all nodes of one list in the hash set.

In an interview, the follow-up question would almost certainly be: "Can you solve this with $O(1)$ space complexity?"

3. Approach 2: The Length Difference Method

To achieve $O(1)$ space, we need to eliminate the HashSet. This requires a more creative use of pointers.

Consider why a simple parallel traversal (moving one pointer in each list simultaneously) doesn't work: if the lists have different lengths before the intersection, the pointers will be out of sync.

The key insight for this approach is to compensate for the length difference.

1. Calculate Lengths: Traverse both lists to find their lengths, $L_1$ and $L_2$.
2. Find Difference: Calculate the absolute difference, $d=|L_1-L_2|$.
3. Align Pointers: Move the pointer of the longer list forward by $d$ nodes.
4. Traverse Together: Now that both pointers are equidistant from the end of their respective lists, traverse both lists simultaneously. The node at which the two pointers become equal is the intersection point.

This method is also explained well in the 'take U forward' video.

Complexity Analysis

• Time Complexity: $O(L_1+L_2)$. You traverse both lists to find lengths, then traverse them again.
• Space Complexity: $O(1)$. We only use a few pointers and variables.

This is a great solution! It meets the space complexity requirement. However, there's an even more elegant and concise way to solve this, which is often considered the "gold standard" solution in interviews.

4. Approach 3: The Optimal Two-Pointer Technique

This final approach is brilliant because it cleverly equalizes the traversal paths of the two pointers without explicitly calculating the lengths first.

Here's the algorithm:

1. Initialize two pointers, ptrA at headA and ptrB at headB.
2. Traverse both lists. In each step of a while loop, advance ptrA and ptrB by one node.
3. Here's the trick: If ptrA reaches the end of List A (null), redirect it to headB. Similarly, if ptrB reaches the end of List B, redirect it to headA.
4. The loop continues until ptrA and ptrB are equal. The node they meet at is the intersection. If they never intersect, they will both become null at the same time, and the loop will terminate, correctly returning null.

Why does this work?
Imagine the total path ptrA travels: it's the length of List A plus the length of List B's unique part. The total path ptrB travels is the length of List B plus the length of List A's unique part.

• Path of ptrA: (length of A's unique part) + (length of common part) + (length of B's unique part)
• Path of ptrB: (length of B's unique part) + (length of common part) + (length of A's unique part)

The paths are identical in composition and length! By having them traverse each other's paths after their own, they are guaranteed to meet at the intersection.

The following resource provides a fantastic explanation and a step-by-step walkthrough of this intuition.

Java Implementation

The implementation for this approach is surprisingly concise.

Here's the core of the Java code, which you'll find in the resources:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptrA = headA;
        ListNode ptrB = headB;

        // The loop terminates when ptrA == ptrB.
        // This will be the intersection node, or null if they don't intersect.
        while (ptrA != ptrB) {
            // If ptrA reaches the end, redirect it to headB. Otherwise, advance it.
            ptrA = (ptrA == null) ? headB : ptrA.next;

            // If ptrB reaches the end, redirect it to headA. Otherwise, advance it.
            ptrB = (ptrB == null) ? headA : ptrB.next;
        }
        
        return ptrA; // or ptrB, they are the same
    }
}

Complexity Analysis

• Time Complexity: $O(L_1+L_2)$. In the worst case, each pointer travels through both lists.
• Space Complexity: $O(1)$.

Conclusion

Excellent work! You have now explored three different ways to solve this problem, progressing from a simple, space-consuming method to a highly efficient and clever constant-space solution. This progression mimics the thought process expected in a technical interview.

Key Takeaways:

• Problem-Solving Trajectory: It's often best to start with a brute-force or simple solution (like hashing) and then optimize for time or space.
• Length-Difference Technique: Aligning pointers by accounting for path length differences is a valid $O(1)$ space strategy.
• Optimal Two-Pointer Swap: The most elegant solution involves making the pointers traverse a combined path (A + B and B + A), which cleverly handles length differences without explicit calculation. This is a pattern worth remembering.

Preview of the next lesson:
We will continue to hone our pointer manipulation skills. In the next lesson, you will learn to merge two sorted linked lists iteratively. This is another foundational problem that is a building block for more complex algorithms like merge sort on linked lists.