Intersection of Two Linked Lists: Multiple Solutions and Complexity Analysis

Understanding the Intersection of Two Linked Lists

The intersection of two linked lists refers to a node where two separate singly linked lists merge into a single, shared sequence. Formally, given two linked lists listA and listB, they are said to intersect if they share at least one common node by reference (not just by value). After the intersection point, both lists follow the exact same chain of nodes until they terminate.

This means that if you traverse both lists starting from their heads, eventually both traversals will land on the same memory address — the intersection node. Once they merge, they stay merged; the lists do not diverge again. The problem typically asks you to return the intersection node itself, or null/None if no intersection exists.

Consider this visual representation:

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

Here, c1 is the intersection node. Everything after c1 is shared by both lists. The challenge is to find c1 efficiently, often with constraints like O(n) time and O(1) memory.

Why This Problem Matters

This is far more than an academic exercise. The intersection of two linked lists problem appears frequently in technical interviews at companies like Amazon, Google, Microsoft, and Meta. Interviewers use it to assess your understanding of pointer manipulation, time-space tradeoffs, and algorithmic intuition.

Beyond interviews, the problem models real-world scenarios:

• File system paths: Two absolute paths may share a common suffix (like a shared directory structure), analogous to intersecting linked lists.
• Version control history: Two git branches may diverge from a common ancestor commit, then later merge back — the merge commit is essentially an intersection.
• Network routing: Two routes may converge at a common router and follow identical subsequent hops.
• Memory deduplication: Detecting shared suffixes allows systems to store data once instead of duplicating identical tails.
• Object lifecycle tracking: In garbage-collected languages, objects with shared ownership graphs resemble intersecting reference chains.

Node Definition

Before diving into solutions, let's establish the standard singly linked list node structure used throughout the examples:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

All solutions will accept two head nodes headA and headB and return the intersecting ListNode or None.

Solution 1: Brute Force — Compare Every Node Pair

The most straightforward approach is to iterate over every node in the first list and, for each, iterate over every node in the second list, comparing them by reference. If a match is found, return it immediately. This is intuitive but inefficient for long lists.

Algorithm Steps

• Start a pointer currA at headA.
• For each node in list A, start a pointer currB at headB.
• Traverse list B entirely, comparing currA to each currB node by reference (is in Python, == for object identity in Java).
• If a reference match is found, return that node.
• If the outer loop completes without finding a match, return None.

Code

def get_intersection_brute_force(headA, headB):
    currA = headA
    while currA:
        currB = headB
        while currB:
            if currA is currB:  # reference equality
                return currA
            currB = currB.next
        currA = currA.next
    return None

Complexity Analysis

• Time Complexity: O(m × n) where m and n are the lengths of lists A and B respectively. In the worst case (no intersection), every pair of nodes is compared.
• Space Complexity: O(1) — only two pointers are used regardless of input size.

This solution is rarely acceptable in practice for lists longer than a few hundred nodes. Its quadratic time complexity makes it impractical for large datasets.

Solution 2: Hash Set — Store References

A significant improvement trades some memory for speed. By storing every node reference from the first list in a hash set, we can then traverse the second list and check for membership in O(1) amortized time per node.

Algorithm Steps

• Initialize an empty hash set seen.
• Traverse list A from head to tail, adding each node object (not value) to seen.
• Traverse list B. For each node, check if it exists in seen.
• The first node found in seen is the intersection; return it.
• If the traversal of B finishes without a match, return None.

Code

def get_intersection_hash_set(headA, headB):
    seen = set()
    
    curr = headA
    while curr:
        seen.add(curr)
        curr = curr.next
    
    curr = headB
    while curr:
        if curr in seen:
            return curr
        curr = curr.next
    
    return None

Complexity Analysis

• Time Complexity: O(m + n) — we traverse list A once (O(m)) and list B once (O(n)), with O(1) set operations per node.
• Space Complexity: O(m) — in the worst case we store all nodes of list A in the hash set.

This solution is often perfectly acceptable in real-world scenarios where memory is abundant. It's straightforward, easy to explain, and linear in time. However, interviewers frequently push for O(1) space, leading us to the two-pointer technique.

Solution 3: Two-Pointer Technique — Optimal O(1) Space

The most elegant solution uses two pointers that traverse both lists, effectively "equalizing" the length discrepancy by cycling through the lists. This achieves O(m + n) time and O(1) space, meeting the strictest constraints.

Core Insight

If two lists have different lengths, their tails are not aligned when you start traversing from both heads simultaneously. However, if you make each pointer traverse the entire length of both lists (list A + list B), both pointers will travel the same total distance. By the time they reach the intersection (or both reach null), they will have synchronized.

Here's the key idea: pointer pA starts at headA and traverses list A, then switches to list B. Pointer pB starts at headB and traverses list B, then switches to list A. If an intersection exists, they will meet exactly at the intersection node. If not, they will both reach None at the same time after traversing m + n nodes each.

Algorithm Steps

• Initialize pA = headA and pB = headB.
• While pA and pB are not equal (by reference):
• • If pA reaches the end of list A, redirect it to headB; otherwise advance to pA.next.
• • If pB reaches the end of list B, redirect it to headA; otherwise advance to pB.next.
• When the loop exits, return pA (or pB, they are equal). This is either the intersection node or None.

Why It Works: A Detailed Walkthrough

Let's trace the example from earlier:

List A: a1 → a2 → c1 → c2 → c3  (length 5, pre-intersection = 2)
List B: b1 → b2 → b3 → c1 → c2 → c3  (length 6, pre-intersection = 3)

Pointer pA path: a1 → a2 → c1 → c2 → c3 → null → b1 → b2 → b3 → c1

Pointer pB path: b1 → b2 → b3 → c1 → c2 → c3 → null → a1 → a2 → c1

Notice: pA takes 2 steps to reach the intersection in its own list, then 3 more to reach null, then 3 steps in list B to reach c1 again — total 8 steps. pB takes 3 steps to reach intersection, then 2 more to reach null, then 2 steps in list A to reach c1 again — total 8 steps. They converge exactly at c1.

If there is no intersection, both pointers traverse exactly m + n nodes and land on None simultaneously, terminating the loop.

Code

def get_intersection_two_pointers(headA, headB):
    if not headA or not headB:
        return None
    
    pA, pB = headA, headB
    
    # Loop until they meet (intersection or both None)
    while pA is not pB:
        # If pA reaches end, switch to headB; else advance
        pA = headB if pA is None else pA.next
        # If pB reaches end, switch to headA; else advance
        pB = headA if pB is None else pB.next
    
    return pA  # Could be intersection node or None

Important Edge Case: Infinite Loop Prevention

Some implementations use a counter or flag to detect cycles after one full pass. The above code naturally handles this because if there is no intersection, both pointers will eventually become None at the same iteration. Specifically, pA becomes None after traversing list A, then switches to list B; pB becomes None after list B, then switches to list A. After both have switched, they traverse the opposite lists and reach None again simultaneously. The condition pA is not pB becomes False when both are None, so the loop terminates correctly.

Complexity Analysis

• Time Complexity: O(m + n) — each pointer traverses at most m + n nodes (each visits all nodes of both lists exactly once).
• Space Complexity: O(1) — only two pointers are used, regardless of list lengths.

This is the gold standard for interview settings and production code where memory constraints are tight.

Solution 4: Length Difference Approach

An alternative O(1) space method makes the logic more explicit by first computing the lengths of both lists, then advancing the longer list's pointer by the difference so both pointers start equidistant from the end. This is equally optimal in complexity and sometimes easier to reason about.

Algorithm Steps

• Compute the length of list A (lenA) and list B (lenB).
• Set pA = headA and pB = headB.
• If lenA > lenB, advance pA by lenA - lenB steps.
• If lenB > lenA, advance pB by lenB - lenA steps.
• Now both pointers are the same distance from their respective list ends. Traverse both lists together one node at a time until they point to the same node (intersection) or both reach None.
• Return the common node (or None).

Code

def get_length(node):
    count = 0
    while node:
        count += 1
        node = node.next
    return count

def get_intersection_length_diff(headA, headB):
    lenA = get_length(headA)
    lenB = get_length(headB)
    
    pA, pB = headA, headB
    
    # Advance the pointer of the longer list
    if lenA > lenB:
        for _ in range(lenA - lenB):
            pA = pA.next
    else:
        for _ in range(lenB - lenA):
            pB = pB.next
    
    # Now traverse together
    while pA is not pB:
        pA = pA.next
        pB = pB.next
    
    return pA  # Intersection node or None

Complexity Analysis

• Time Complexity: O(m + n) — two passes to compute lengths (O(m + n)), plus one synchronized pass (O(min(m, n)) in the worst case), which simplifies to O(m + n).
• Space Complexity: O(1) — only integer counters and pointers.

This approach makes the "equalization" explicit. It's a good fallback if the two-pointer cycling logic feels tricky to explain on the spot.

Complexity Analysis Summary

Here is a side-by-side comparison of all four approaches:

┌─────────────────────────┬────────────────┬────────────────┬──────────────────────┐
│ Approach                │ Time Complexity│ Space Complexity│ Notes                │
├─────────────────────────┼────────────────┼────────────────┼──────────────────────┤
│ Brute Force             │ O(m × n)       │ O(1)           │ Simple, impractical  │
│                         │                │                │ for large lists      │
├─────────────────────────┼────────────────┼────────────────┼──────────────────────┤
│ Hash Set                │ O(m + n)       │ O(m)           │ Good balance,        │
│                         │                │                │ memory-intensive     │
├─────────────────────────┼────────────────┼────────────────┼──────────────────────┤
│ Two-Pointer (Cycling)   │ O(m + n)       │ O(1)           │ Elegant, optimal,    │
│                         │                │                │ tricky to explain    │
├─────────────────────────┼────────────────┼────────────────┼──────────────────────┤
│ Length Difference       │ O(m + n)       │ O(1)           │ Explicit equalization│
│                         │                │                │ easier to follow     │
└─────────────────────────┴────────────────┴────────────────┴──────────────────────┘

Edge Cases and Best Practices

Critical Edge Cases

• One or both lists are empty: Return None immediately. The two-pointer solution handles this naturally if you check for null heads upfront, though the loop version also works because both start as None.
• Intersection at the head: If both lists share the same head node, the algorithms should detect it on the first comparison. The two-pointer solution will return it on the first iteration.
• No intersection: All solutions must return None. The two-pointer cycling approach must be verified to not loop infinitely — it won't, because both pointers reach None simultaneously after m + n steps.
• Lists of equal length: The two-pointer approach works identically; no "switching" may be needed if the intersection is found early, but the logic remains correct.
• Intersection is the last node: The algorithms correctly return the last node before null. After the intersection, both lists terminate together.

Best Practices for Production Code

• Favor readability over cleverness: The hash set solution is perfectly valid in most contexts. Use it unless you have measured memory pressure.
• Use reference equality, not value equality: Always compare node objects by identity (is in Python, == on object references in Java/C#). Two nodes with the same value are not an intersection unless they occupy the same memory address.
• Add early termination checks: If either head is null, return null immediately to avoid unnecessary computation.
• Write unit tests for all edge cases: Test empty lists, single-node lists, intersection at head, intersection at tail, and no intersection.
• Consider immutability: If the lists should not be modified, ensure your traversal doesn't alter node pointers. All solutions presented here are read-only.
• Document your choice: If using the two-pointer technique, add a brief comment explaining the cycling logic — future maintainers will thank you.

Sample Test Harness

# Helper to build intersecting lists for testing
def build_intersecting_lists():
    # Shared tail
    c3 = ListNode(8)
    c2 = ListNode(7, c3)
    c1 = ListNode(6, c2)  # intersection node
    
    # List A: 1 → 2 → 6 → 7 → 8
    a2 = ListNode(2, c1)
    a1 = ListNode(1, a2)
    
    # List B: 3 → 4 → 5 → 6 → 7 → 8
    b3 = ListNode(5, c1)
    b2 = ListNode(4, b3)
    b1 = ListNode(3, b2)
    
    return a1, b1, c1

# Quick validation
headA, headB, expected = build_intersecting_lists()
result = get_intersection_two_pointers(headA, headB)
print("Intersection node value:", result.val if result else None)  # Should print 6
print("Test passed:", result is expected)

Conclusion

The intersection of two linked lists is a classic problem that elegantly tests your ability to think about pointer manipulation, time-memory tradeoffs, and algorithmic optimization. We explored four distinct solutions — from the naive O(m × n) brute force to the optimal O(m + n) O(1) two-pointer technique. Each approach has its place: brute force for tiny inputs, hash set for rapid prototyping with generous memory, length difference for explicit clarity, and two-pointer cycling for the most memory-constrained environments. Understanding all four equips you with a toolkit to choose the right tradeoff for any context, whether in an interview, a code review, or a production system handling millions of nodes.