Intersection of Two Linked Lists | Leetcode 160

Welcome to our breakdown of Intersection of Two Linked Lists (Leetcode 160). This is a beautiful linked list synchronization conundrum. Due to mismatched list lengths, standard iteration pointers drift out of alignment immediately!

Problem Statement

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

Note: You must retain the original structure natively, and the absolute intersection is defined completely by exact Memory Reference, not just Value.

Example:

A:        a1 → a2
                 ↘
                  c1 → c2 → c3
                 ↗
B:  b1 → b2 → b3

Output: Node c1

Approach 1: HashSet Verification O(N+M) Space

If we want the pure brute-force naive strategy, we can physically save the memory addresses!

We traverse the entirety of List A, pushing every exact unique memory node structurally into our Set. Then, we traverse List B. The absolute first time we hit a node that mathematically registers as natively existing inside our internal Set, we've discovered the physical merger!

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        visited_nodes = set()
        
        # Traverse list A entirely natively
        curr_a = headA
        while curr_a:
            visited_nodes.add(curr_a)
            curr_a = curr_a.next
            
        # Scan B checking against the cache hash entries
        curr_b = headB
        while curr_b:
            if curr_b in visited_nodes:
                return curr_b
            curr_b = curr_b.next
            
        return None

Complexity Analysis

Approach 2: Pointer Loop Translation O(1) Space

The reason we can't just iterate normally is that the list leading up to the convergence might be geometrically mismatched in distance. (List A might have 2 nodes before convergence, List B might have 5!)

The Trick: What if Pointer A traces List A, hits the end, and implicitly transitions magically to the head of List B? And Pointer B traces List B, hits its end, and magically resets to List A?

Let the total length of the unique segments be X for A, and Y for B. Let the shared convergence segment be Z. If Pointer A runs sequentially through X + Z + Y + Z ... and B runs Y + Z + X + Z... They have traveled the absolute exact equivalent physical distance! Therefore, on their second cycle, they will effortlessly crash into each other at the exact mathematical point of convergence precisely simultaneously!

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB: return None
        
        ptr_a = headA
        ptr_b = headB
        
        # When ptr_a == ptr_b natively, we've found it!
        # If no intersection natively exists, they will both hit None physically simultaneously and exit!
        while ptr_a != ptr_b:
            # If pointer A hits the tail of A, dynamically reset it to the absolute head of B!
            ptr_a = ptr_a.next if ptr_a else headB
            # If pointer B hits the tail of B, loop it to the start of A!
            ptr_b = ptr_b.next if ptr_b else headA
            
        return ptr_a

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (160)