L12: Find the Intersection Point of Y Linked Lists

Finding the intersection point of two singly linked lists (often referred to as a "Y-shaped Linked List") is a classic algorithm and data structures problem frequently asked in technical interviews. The objective is to determine the exact node where two separate linked lists merge into a single shared sequence, or return null if they never intersect.

1. Problem Statement & Conceptual Overview

Given the head nodes of two singly linked lists (head1 and head2), our task is to find and return the first common node where the two lists merge.

Visualizing the Y-Shape

Key Behavioral Scenarios

• Intersecting Lists: The two lists run independently for a period and then merge into a single shared tail. We must return the exact memory address of the first node where they merge.
• Non-Intersecting (Parallel/Diverging) Lists: The lists never touch or collide. In this case, the algorithm must return null.
• Identical Node Values vs. Node Identity: Note that we are looking for the same node instance (memory address), not just nodes with identical integer data values. Two different nodes might both hold the value 4, but that does not make them an intersection point.

2. Approach 1: The Brute-Force Hashing Solution

The most intuitive, brute-force way to approach this problem is to use extra memory to memorize the nodes of the first list, then scan the second list to find the first match.

Algorithm Steps

1. Initialize a pointer temp1 at head1 and an auxiliary hash map (or hash set).
2. Traverse the entire first linked list (head1), storing every node object (not its integer value) into the hash map.
3. Reset a pointer temp2 to head2 and traverse the second linked list.
4. For each node visited in the second list, check if it already exists in the hash map.
5. The first node you encounter that exists in the map is your intersection point. Return it immediately.
6. If you reach null without finding a match, return null.

Pseudo-Code Implementation

def getIntersectionNode_hashing(head1, head2):
    node_map = {}
    temp1 = head1
    
    # Store all nodes of list 1 in the map
    while temp1 is not None:
        node_map[temp1] = True
        temp1 = temp1.next
        
    temp2 = head2
    # Check nodes of list 2 against the map
    while temp2 is not None:
        if temp2 in node_map:
            return temp2  # First common node found
        temp2 = temp2.next
        
    return None  # No intersection

Complexity Analysis

• Time Complexity: $\mathcal{O}(N_1 \cdot \text{map\_op} + N_2 \cdot \text{map\_op})$, where $N_1$ and $N_2$ are the lengths of the two linked lists. If using a hash set with $\mathcal{O}(1)$ average insertions and lookups, the overall time complexity is $\mathcal{O}(N_1 + N_2)$.
• Space Complexity: $\mathcal{O}(N_1)$ (or $\mathcal{O}(N_2)$ depending on which list you store) because we allocate extra memory for the hash map to store node references.

Note: While this approach works, interviewers will typically reject it because of the $\mathcal{O}(N)$ auxiliary space complexity. We need to optimize the space complexity down to $\mathcal{O}(1)$.

3. Approach 2: The Length-Difference Optimization (Two-Pointer Technique)

To solve the problem with constant extra space ($\mathcal{O}(1)$), we must align the starting positions of both pointers so they reach the intersection node simultaneously.

Core Mental Model

If two runners are running at the same speed, but one starts further back than the other, they will never finish or align correctly unless we compensate for the head start. By calculating the exact length of both lists, we can determine the difference in length and advance the pointer of the longer list forward by that exact difference.

Step-by-Step Evolution

1. Traverse head1 to compute its length $N_1$.
2. Traverse head2 to compute its length $N_2$.
3. Find the absolute difference: $D = \vert N_1 - N_2\vert$.
4. Take two pointers (t1 and t2) and place them at head1 and head2 respectively.
5. Move the pointer of the longer list forward by $D$ steps.
6. Now, advance both pointers simultaneously node-by-node. The first node where t1 == t2 is your intersection point.

Implementation Logic

def getIntersectionNode_lengthDiff(head1, head2):
    # Step 1: Compute lengths
    n1, n2 = 0, 0
    t1, t2 = head1, head2
    
    while t1:
        n1 += 1
        t1 = t1.next
    while t2:
        n2 += 1
        t2 = t2.next
        
    t1, t2 = head1, head2
    
    # Step 2: Advance the pointer of the longer list
    if n1 < n2:
        d = n2 - n1
        for _ in range(d):
            t2 = t2.next
    else:
        d = n1 - n2
        for _ in range(d):
            t1 = t1.next
            
    # Step 3: Simultaneous traversal until intersection
    while t1 != t2:
        t1 = t1.next
        t2 = t2.next
        
    return t1  # Returns intersection node or None

Complexity Analysis

• Time Complexity: $\mathcal{O}(N_1 + N_2 + \vert N_1 - N_2\vert + \min(N_1, N_2))$, which simplifies to $\mathcal{O}(N_1 + N_2)$ because we traverse both lists to find lengths, traverse the difference, and finally traverse up to the intersection.
• Space Complexity: $\mathcal{O}(1)$ as only a few pointer variables are used.

4. Approach 3: The Optimal Two-Pointer Switching Technique

Can we avoid calculating lengths entirely and still achieve $\mathcal{O}(N_1 + N_2)$ time and $\mathcal{O}(1)$ space? Yes! This is the most elegant solution expected in advanced interviews.

Core Mental Model: The Track Lap Analogy

Imagine two runners running around two tracks of different lengths that eventually merge into a shared track.

• Runner 1 runs around Track 1 (length $A$) and when they hit the end, they are instantly transported to the start of Track 2.
• Runner 2 runs around Track 2 (length $B$) and when they hit the end, they are instantly transported to the start of Track 1.
• Because both runners travel a total distance equal to $A + B$ before meeting, they are guaranteed to arrive at the intersection point at the exact same time, perfectly neutralizing the length discrepancy!

Step-by-Step Flow Walkthrough

1. Initialize temp1 = head1 and temp2 = head2.
2. Run a loop while temp1 != temp2:
   • Move temp1 forward (temp1 = temp1.next). If temp1 hits null, redirect it to head2.
   • Move temp2 forward (temp2 = temp2.next). If temp2 hits null, redirect it to head1.
3. If the lists intersect, temp1 and temp2 will meet at the intersection node and terminate the loop.
4. If the lists do not intersect, both pointers will traverse both lists, reach null simultaneously at the end of their second pass, and exit the loop returning null.

5. Complete Code Implementations (Optimal Approach)

Here is the robust, production-grade implementation of the optimal pointer-switching algorithm across popular programming languages.

Java Implementation

public class Solution {
    public ListNode getIntersectionNode(ListNode head1, ListNode head2) {
        // Edge case: if either list is empty, there is no intersection
        if (head1 == null || head2 == null) return null;
        
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        
        // Traverse until both pointers meet at the intersection or null
        while (temp1 != temp2) {
            // Move temp1 to next, or switch to head2 if end is reached
            temp1 = (temp1 != null) ? temp1.next : head2;
            
            // Move temp2 to next, or switch to head1 if end is reached
            temp2 = (temp2 != null) ? temp2.next : head1;
        }
        
        // Returns either the intersection node or null (if no collision)
        return temp1;
    }
}

Python Implementation

class Solution:
    def getIntersectionNode(self, head1: ListNode, head2: ListNode) -> ListNode:
        if not head1 or not head2:
            return None
            
        temp1 = head1
        temp2 = head2
        
        while temp1 != temp2:
            temp1 = temp1.next if temp1 else head2
            temp2 = temp2.next if temp2 else head1
            
        return temp1

6. Real-World Practical Pitfalls & Edge Cases

When writing or testing this code in production, keep these edge cases in mind:

Summary and Key Takeaways

• Problem Definition: Finding the first common memory reference (node) where two singly linked lists merge into a Y-shape.
• Value vs. Reference: Always compare node objects/memory addresses (temp1 == temp2), never their internal data values (temp1.val == temp2.val).
• Brute-Force (Hashing): Store all nodes of the first list in a hash map, then scan the second list. Time: $\mathcal{O}(N_1 + N_2)$, Space: $\mathcal{O}(N_1)$. Rejected by strict interviewers due to extra space.
• Length-Difference Approach: Compute lengths $N_1$ and $N_2$, advance the longer list by the absolute difference $D = \vert N_1 - N_2\vert$, then march together. Time: $\mathcal{O}(N_1 + N_2)$, Space: $\mathcal{O}(1)$.
• Optimal Pointer-Switching Approach: Traverse both lists simultaneously. When a pointer reaches null, redirect it to the head of the opposite list. This elegantly neutralizes the length difference in exactly two passes.
• Optimal Complexity: Time complexity is strictly $\mathcal{O}(N_1 + N_2)$ and space complexity is $\mathcal{O}(1)$.
• Non-Collision Handling: If no intersection exists, both pointers will traverse both lists and terminate at null at the exact same moment.