Two-Pointer Techniques - Learning Module

Loading content...

0/276

Detecting Intersection of Two Lists

When Two Paths Converge

Imagine two river tributaries that flow separately for miles before merging into a single river. Once merged, they flow together as one. Linked lists can exhibit the same structure: two separate chains that, at some point, share a common tail.

This intersection pattern appears frequently in real systems:

Memory management: Two data structures might share a common suffix to save memory
Version control: Branches in a commit graph merge at common ancestors
Document editing: Multiple undo stacks might share common history
Network routing: Multiple paths might converge at a common gateway

Detecting whether two linked lists intersect—and finding where—is a classic problem that showcases the elegance of pointer manipulation. In this page, we'll explore multiple solutions and understand why the two-pointer approach achieves optimal O(n) time with O(1) space.

What You Will Learn

By the end of this page, you will understand multiple approaches to detecting list intersection, from naive to optimal. You'll learn the elegant two-pointer solution, understand its mathematical basis, and be able to handle all edge cases correctly.

Problem Definition and Constraints

Formal Problem Statement

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

Critical Constraint: The lists must not have cycles. If they did and intersected, the shared portion would include the cycle, making both lists effectively cyclic.

Intersection Definition

Two lists intersect if they share a common node by reference (same memory location), not just by value. From the intersection point onward, both lists are identical—they share the same tail.

Converting Mermaid diagram...

In the diagram above:

List A: A1 → A2 → A3 → C1 → C2 → C3 (total length 6, 3 unique + 3 shared)
List B: B1 → B2 → C1 → C2 → C3 (total length 5, 2 unique + 3 shared)
Intersection node: C1

Key Observations:

Lists can have different lengths before the intersection
Once intersected, the tails are identical (same nodes, same length)
If no intersection, both lists end at different nulls

Value vs Reference

Intersection means the exact same node object in memory, not just nodes with equal values. [1,2,3] and [1,2,3] are not intersecting unless they literally share node references. Always compare node identity (===, ==, or 'is'), not node values.

Approach 1: Hash Set Solution

The most straightforward approach uses a hash set to record all nodes in one list, then checks if any node from the other list appears in the set.

Algorithm:

Traverse List A, adding each node to a hash set
Traverse List B, checking if each node exists in the set
The first duplicate found is the intersection

Complexity:

Time: O(m + n) where m and n are list lengths
Space: O(m) or O(n) depending on which list we store

intersection_hashset.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def get_intersection_hashset(headA: ListNode, headB: ListNode) -> ListNode:
    """
    Find intersection using a hash set.
    
    Time: O(m + n)
    Space: O(m) - stores all nodes from first list
    """
    if not headA or not headB:
        return None
    
    # Store all nodes from List A
    nodes_in_a = set()
    current = headA
    
    while current:
        nodes_in_a.add(current)  # Add node reference, not value
        current = current.next
    
    # Check each node in List B
    current = headB
    
    while current:
        if current in nodes_in_a:
            return current  # First common node = intersection
        current = current.next
    
    return None  # No intersection

When Hash Set is Appropriate

The hash set approach is perfectly valid when space isn't constrained and implementation simplicity is valued. It's also easily adaptable: you can record additional information like distance from head. However, for optimal space complexity, we need a different approach.

Approach 2: Length Difference Method

A more space-efficient approach uses the observation that the tails have equal length. If we align the lists so both pointers have equal distance to the end, we can walk them together and find the intersection.

Key Insight:

If List A has length m and List B has length n
The difference is |m - n|
Advancing the longer list's pointer by |m - n| nodes aligns them
Then walking together, the first common node is the intersection

intersection_length.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def get_intersection_by_length(headA: ListNode, headB: ListNode) -> ListNode:
    """
    Find intersection by aligning lists based on length difference.
    
    Time: O(m + n)
    Space: O(1)
    """
    if not headA or not headB:
        return None
    
    # Step 1: Calculate lengths
    def get_length(head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length
    
    len_a = get_length(headA)
    len_b = get_length(headB)
    
    # Step 2: Align starting positions
    # Advance the longer list by the difference
    ptr_a = headA
    ptr_b = headB
    
    if len_a > len_b:
        for _ in range(len_a - len_b):
            ptr_a = ptr_a.next
    else:
        for _ in range(len_b - len_a):
            ptr_b = ptr_b.next
    
    # Step 3: Walk together until intersection or end
    while ptr_a and ptr_b:
        if ptr_a == ptr_b:
            return ptr_a  # Intersection found
        ptr_a = ptr_a.next
        ptr_b = ptr_b.next
    
    return None  # No intersection
 
 
# Example trace:
# List A: 1 → 2 → 3 → 4 → 5 (length 5)
# List B: 8 → 9 → 4 → 5     (length 4, intersects at 4)
#
# len_a=5, len_b=4, difference=1
# Advance ptr_a by 1: now at node 2
# Walk together:
#   ptr_a=2, ptr_b=8 (not equal)
#   ptr_a=3, ptr_b=9 (not equal)
#   ptr_a=4, ptr_b=4 (EQUAL! intersection found)

Length Difference Method Breakdown
Step	Action	Time
1	Traverse List A to get length	O(m)
2	Traverse List B to get length	O(n)
3	Advance longer list by difference	O(\|m-n\|)
4	Walk together until intersection	O(min(m,n))
Total	—	O(m + n)

Three Traversals

This method traverses each list at most twice: once to count, once to find intersection. While still O(m+n), the constant factor is slightly higher than the elegant two-pointer approach we'll see next.

Approach 3: The Elegant Two-Pointer Solution

The most elegant solution uses two pointers that switch lists when they reach the end. This automatically compensates for the length difference without explicitly calculating it.

The Brilliant Insight:

Consider two pointers, A and B, starting at headA and headB:

When A reaches the end of List A, redirect it to headB
When B reaches the end of List B, redirect it to headA
If the lists intersect, they will meet at the intersection
If they don't intersect, they will both become null simultaneously

Why This Works:

Let's denote:

Length of unique part of A = a
Length of unique part of B = b
Length of shared tail = c

Total length of A = a + c Total length of B = b + c

Pointer A travels: (a + c) on A, then b on B = a + c + b Pointer B travels: (b + c) on B, then a on A = b + c + a

They travel the same total distance! After traveling a + b + c, both pointers arrive at the intersection node (or null if no intersection).

intersection_two_pointer.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def get_intersection_node(headA: ListNode, headB: ListNode) -> ListNode:
    """
    Find intersection using the two-pointer list-switching technique.
    
    The two pointers travel equal total distances:
    - Pointer A: traverses A, then B
    - Pointer B: traverses B, then A
    
    If intersection exists, they meet at the intersection.
    If no intersection, they both become null simultaneously.
    
    Time: O(m + n)
    Space: O(1)
    """
    if not headA or not headB:
        return None
    
    ptrA = headA
    ptrB = headB
    
    # Continue until they meet (intersection or both null)
    while ptrA != ptrB:
        # When reaching end, switch to the other list
        ptrA = ptrA.next if ptrA else headB
        ptrB = ptrB.next if ptrB else headA
    
    # ptrA == ptrB: either intersection node or null
    return ptrA
 
 
# Trace example (with intersection):
# A: a1 → a2 → c1 → c2 → c3 (length 5, a=2, c=3)
# B: b1 → b2 → b3 → c1 → c2 → c3 (length 6, b=3, c=3)
#
# Step  ptrA    ptrB
# 0     a1      b1
# 1     a2      b2
# 2     c1      b3
# 3     c2      c1
# 4     c3      c2
# 5     null    c3
# 6     b1      null
# 7     b2      a1
# 8     b3      a2
# 9     c1      c1  ← INTERSECTION FOUND!
#
# Total steps: a + c + b = 2 + 3 + 3 = 8 for ptrA
#              b + c + a = 3 + 3 + 2 = 8 for ptrB

The Beauty of Equal Path Lengths

By switching lists, both pointers travel a + b + c total. If there's an intersection (c > 0), they meet there. If no intersection (c = 0), both travel a + b and become null together. The algorithm elegantly handles both cases with the same code.

Mathematical Analysis

Let's rigorously prove why the two-pointer technique correctly finds the intersection.

Setup

Define:

a = number of nodes in List A before intersection
b = number of nodes in List B before intersection
c = number of nodes in shared tail (0 if no intersection)
m = a + c (total length of A)
n = b + c (total length of B)

Case 1: Intersection Exists (c > 0)

Pointer A travels:

First, through A: a + c nodes (reaches null)
Then, through B: b nodes (reaches intersection)

Total for A: a + c + b = a + b + c

Pointer B travels:

First, through B: b + c nodes (reaches null)
Then, through A: a nodes (reaches intersection)

Total for B: b + c + a = a + b + c

Both travel the same distance and meet at the intersection!

intersection_proof.txt
Proof: Two-Pointer Intersection Algorithm
 
Case 1: Lists Intersect (c > 0)
===============================
List A: [----a nodes----][----c nodes----]
List B:      [----b nodes----][----c nodes----]
                              ↑
                        Intersection
 
Pointer A path: A's (a+c) → B's b → meets at intersection
Pointer B path: B's (b+c) → A's a → meets at intersection
 
Distance A = (a + c) + b = a + b + c
Distance B = (b + c) + a = a + b + c  ✓ Equal!
 
Meeting point: After a + b + c steps, both are at intersection.
 
 
Case 2: Lists Don't Intersect (c = 0)
=====================================
List A: [----a nodes----] → null
List B: [----b nodes----] → null
 
Pointer A path: A's a → null → B's b → null
Pointer B path: B's b → null → A's a → null
 
Distance A = a + 1 (null) + b + 1 (null)
Distance B = b + 1 (null) + a + 1 (null)
 
After a + b + 2 steps (counting nulls as steps):
- ptrA is null (finished B)
- ptrB is null (finished A)
- ptrA == ptrB == null ✓
 
The loop exits when ptrA == ptrB, which is null.
Correctly returns null (no intersection).

Termination Guarantee

The algorithm always terminates in at most 2(m + n) iterations:

In the intersection case: terminates after a + b + c iterations
In the no-intersection case: terminates after a + b + 2 iterations (visiting both nulls)

Since each pointer switches at most once, total iterations ≤ m + n + max(m, n) ≤ 2(m + n).

Why Null Handling Works

When ptrA becomes null and redirects to headB, it effectively 'adds' list B's full length to its path. But it's not traversing B from scratch—it's aligning so both pointers hit the intersection at the same step. The null transition is the key that compensates for length differences.

Edge Cases and Special Scenarios

The two-pointer algorithm handles all edge cases naturally, but it's important to verify your understanding:

Edge Cases for Intersection Detection
Scenario	Setup	Result	Why It Works
Empty list(s)	headA = null or headB = null	null	Early return before loop
No intersection	Separate lists with no shared nodes	null	Both reach null at same step
Same list	headA == headB	headA	ptrA == ptrB immediately
Intersect at head	B's first node is in A's chain	First shared node	ptrB reaches it while ptrA still traversing
Equal length, intersect	m == n with shared tail	Intersection	No switching needed; meet naturally
One much longer	m >> n or n >> m	Intersection or null	Switching compensates for difference

intersection_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def test_intersection_detection():
    """Comprehensive tests for intersection detection."""
    
    # Test 1: No intersection
    a = ListNode(1, ListNode(2, ListNode(3)))
    b = ListNode(4, ListNode(5))
    assert get_intersection_node(a, b) is None
    print("Test 1 passed: No intersection")
    
    # Test 2: Intersection in middle
    # A: 1 → 2 → 3 → 4
    # B:     5 → 3 → 4 (shares 3→4 with A)
    shared = ListNode(3, ListNode(4))
    a = ListNode(1, ListNode(2, shared))
    b = ListNode(5, shared)
    assert get_intersection_node(a, b) == shared
    print("Test 2 passed: Intersection in middle")
    
    # Test 3: Same list (intersect at head)
    a = ListNode(1, ListNode(2, ListNode(3)))
    assert get_intersection_node(a, a) == a
    print("Test 3 passed: Same list")
    
    # Test 4: Empty lists
    assert get_intersection_node(None, None) is None
    assert get_intersection_node(a, None) is None
    assert get_intersection_node(None, a) is None
    print("Test 4 passed: Empty lists")
    
    # Test 5: Very different lengths
    # A: 1 → 2 → 3 → 4 → 5 → 6 → 7 (length 7)
    # B: 8 → 6 → 7 (shares last 2, length 3)
    shared = ListNode(6, ListNode(7))
    a = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, shared)))))
    b = ListNode(8, shared)
    assert get_intersection_node(a, b) == shared
    print("Test 5 passed: Very different lengths")
    
    # Test 6: Equal lengths, intersect at first node
    shared = ListNode(1, ListNode(2, ListNode(3)))
    assert get_intersection_node(shared, shared) == shared
    print("Test 6 passed: Equal lengths, same list")
    
    print("All intersection tests passed!")

Don't Modify the Lists

The two-pointer algorithm is read-only—it doesn't modify any node's next pointer. Some 'clever' solutions involve cutting and reattaching lists, but these can corrupt data if not restored perfectly. Stick with the clean two-pointer approach.

Alternative Approaches for Special Cases

While the two-pointer technique is optimal for the general case, some variations require different approaches or offer interesting insights.

1. Verify Intersection Without Finding It

If you only need to know whether lists intersect (not where), you can just check if their tails are the same:

check_intersects.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def lists_intersect(headA: ListNode, headB: ListNode) -> bool:
    """
    Check if two lists intersect (without finding intersection).
    
    Key insight: If lists intersect, they have the same tail node.
    
    Time: O(m + n)
    Space: O(1)
    """
    if not headA or not headB:
        return False
    
    # Find tail of List A
    tailA = headA
    while tailA.next:
        tailA = tailA.next
    
    # Find tail of List B
    tailB = headB
    while tailB.next:
        tailB = tailB.next
    
    # Same tail means intersection
    return tailA is tailB

2. Using Cycle Detection (Temporary Modification)

A creative approach: temporarily connect one list's tail to its head, creating a cycle. If the other list intersects, it will also have a cycle. Use Floyd's algorithm to detect it. Then restore the list.

Note: This modifies the list temporarily, which isn't always acceptable.

intersection_via_cycle.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def get_intersection_via_cycle(headA: ListNode, headB: ListNode) -> ListNode:
    """
    Find intersection by creating a temporary cycle.
    
    Algorithm:
    1. Connect List A's tail to List A's head (creates cycle)
    2. Use Floyd's on List B
       - If cycle found, intersection exists
       - Entry point of cycle = intersection node
    3. Restore List A by breaking the cycle
    
    Time: O(m + n)
    Space: O(1)
    
    NOTE: Temporarily modifies List A!
    """
    if not headA or not headB:
        return None
    
    # Find tail of List A and connect to head
    tailA = headA
    while tailA.next:
        tailA = tailA.next
    tailA.next = headA  # Create cycle
    
    # Use Floyd's cycle detection starting from headB
    slow = headB
    fast = headB
    has_cycle = False
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break
    
    intersection = None
    
    if has_cycle:
        # Find cycle entry (same as Floyd's entry finding)
        entry_finder = headB
        while entry_finder != slow:
            entry_finder = entry_finder.next
            slow = slow.next
        intersection = entry_finder
    
    # CRITICAL: Restore List A
    tailA.next = None
    
    return intersection

Prefer the Two-Pointer Method

The cycle-based approach is an interesting application of Floyd's algorithm, but it requires modifying the list (even temporarily), which can cause issues in concurrent environments or when the list is read-only. The standard two-pointer technique is safer and just as efficient.

Comparison of Approaches

Intersection Detection Methods Comparison
Method	Time	Space	Modifies List?	Pros	Cons
Hash Set	O(m+n)	O(m) or O(n)	No	Simple, intuitive	Uses extra memory
Length Difference	O(m+n)	O(1)	No	Clear logic, O(1) space	Three traversals
Two-Pointer Switch	O(m+n)	O(1)	No	Elegant, minimal code	Less intuitive initially
Tail Check (Boolean)	O(m+n)	O(1)	No	Fast for yes/no	Doesn't find intersection node
Cycle Conversion	O(m+n)	O(1)	Yes (temp)	Uses Floyd's skill	Risks corruption

Recommendation by Scenario:

Interview answer: Two-pointer switch (shows elegance and deep understanding)
Production code: Two-pointer switch or length difference (both safe and optimal)
Quick prototype: Hash set (simple and readable)
Concurrent access: Two-pointer switch (no modifications)
Just need yes/no: Tail comparison (simpler for boolean result)

Interview Strategy

In interviews, briefly mention the hash set approach ('naive O(m+n) time, O(m) space'), then immediately pivot to the two-pointer solution. Explain the path-length equality insight. This shows you can identify brute-force solutions and optimize them.

Real-World Applications

Understanding list intersection has applications beyond textbook problems:

Practical Applications

•Git Merge Base: Finding the common ancestor of two branches is conceptually similar—two chains of commits that may share history. Git uses more sophisticated algorithms, but the core idea of 'where do two paths converge' is the same.
•DOM Tree Analysis: In web browsers, determining if two DOM nodes share a common ancestor uses similar techniques. Finding the lowest common ancestor involves comparing paths from nodes to root.
•Database Foreign Keys: When two tables have foreign key chains leading to the same record, detecting this shared reference can optimize queries and prevent redundant data.
•Memory Optimization: Systems that use structural sharing (like persistent data structures) have multiple references pointing to shared suffixes. Detecting these helps with memory analysis and garbage collection.
•Network Topology: Finding where two network paths converge helps with routing optimization, failure analysis, and traffic engineering.
•Linked Data Validation: In data pipelines, verifying that two data streams don't inappropriately share mutable state requires intersection detection.

Pattern Recognition

The intersection problem generalizes to any scenario where you need to find 'where two sequences of linked entities meet.' The two-pointer technique adapts to many such problems—always ask 'can I make both paths equal length by some clever traversal?'

Summary: Detecting Intersection

We've completed our exploration of detecting intersection in linked lists. Let's consolidate the key insights:

Key Takeaways

•Intersection means shared references, not values — Nodes must be the exact same objects in memory.
•The key insight is path length equalization — Both pointers should travel a + b + c total steps to meet.
•List-switching achieves this automatically — When one pointer reaches null, redirect to the other list's head.
•O(m+n) time and O(1) space is optimal — You must visit each node at least once, and no extra storage is needed.
•The algorithm handles no-intersection cleanly — Both pointers become null together after traversing both lists.
•Hash set is acceptable when space isn't constrained — It's simpler to implement and understand.

Module Complete

With this page, we've completed the Two-Pointer Techniques for Linked Lists module. You've mastered:

Slow and Fast Pointer Fundamentals — The core technique with 2:1 speed ratio
Cycle Detection (Floyd's Algorithm) — Detecting, finding entry, and measuring cycles
Finding the Middle Element — Multiple variants for different use cases
Detecting Intersection — Finding where two lists converge

These techniques form a cohesive toolkit for linked list problems. They share a common philosophy: use pointer manipulation creatively to extract structural information without extra space. This module has equipped you with patterns that solve dozens of interview problems and real-world scenarios.

Module Complete

Congratulations! You've mastered the two-pointer techniques for linked lists. These skills—slow/fast pointers, cycle detection, middle-finding, and intersection detection—are among the most frequently tested in technical interviews and most useful in systems programming. Apply them confidently to new problems.