Linked List Intersection & Merge Point

Two linked lists intersect when they share the same physical node — not just a node with the same value, but the exact same object in memory. After the intersection point, both lists share the same tail. Finding where they merge is a classic pointer problem with an elegant O(1) space solution.

Understanding Intersection

List A: A1 → A2 → A3 ↘
                        C1 → C2 → C3 → None
List B:      B1 → B2 ↗

Intersection node: C1
After C1, both lists share C1 → C2 → C3

Important: intersection means the same node object, not just the same value. If A has a node with value 5 and B has a different node with value 5, they do NOT intersect.

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

Approach 1: Hash Set — O(n + m) time, O(n) space

Visit every node in List A, store them in a set. Then walk List B and check:

def get_intersection_hashset(headA, headB):
    """
    Find intersection using a hash set.
    Time: O(n + m), Space: O(n)
    """
    visited = set()

    # Store all nodes from list A
    current = headA
    while current:
        visited.add(id(current))  # Use id() to compare identity
        current = current.next

    # Walk list B, check if any node was seen
    current = headB
    while current:
        if id(current) in visited:
            return current  # Intersection found!
        current = current.next

    return None  # No intersection

This works but uses O(n) extra space. We can do better.

Approach 2: Length Difference — O(n + m) time, O(1) space

If we know the lengths of both lists, we can align them so both pointers reach the intersection at the same time:

def get_length(head):
    """Count nodes in the list."""
    length = 0
    while head:
        length += 1
        head = head.next
    return length


def get_intersection_length(headA, headB):
    """
    Find intersection using length difference.
    Time: O(n + m), Space: O(1)
    """
    lenA = get_length(headA)
    lenB = get_length(headB)

    # Advance the longer list by the difference
    pA, pB = headA, headB
    if lenA > lenB:
        for _ in range(lenA - lenB):
            pA = pA.next
    else:
        for _ in range(lenB - lenA):
            pB = pB.next

    # Now both pointers are equidistant from the intersection
    while pA and pB:
        if pA is pB:
            return pA  # Intersection!
        pA = pA.next
        pB = pB.next

    return None

How it works

List A (length 5): A1 → A2 → A3 → C1 → C2
List B (length 4):      B1 → B2 → C1 → C2

Difference = 5 - 4 = 1
Advance pA by 1: pA starts at A2

Now:
pA: A2 → A3 → C1 → C2
pB: B1 → B2 → C1 → C2

Both travel 3 steps to reach C1 — they meet at the intersection!

Approach 3: Two-Pointer Technique — O(n + m) time, O(1) space

This is the most elegant solution. No need to calculate lengths:

def get_intersection_two_pointer(headA, headB):
    """
    Find intersection using the two-pointer technique.
    Time: O(n + m), Space: O(1)

    Key insight: When pA reaches the end of A, redirect it to headB.
    When pB reaches the end of B, redirect it to headA.
    Both will travel (lenA + lenB) steps total.
    If they intersect, they'll meet at the intersection.
    If not, they'll both reach None at the same time.
    """
    if not headA or not headB:
        return None

    pA = headA
    pB = headB

    # When pA reaches None, redirect to headB (and vice versa)
    while pA is not pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA

    return pA  # Either intersection node or None

Why does this work?

Let’s define:

• a = nodes unique to List A (before intersection)
• b = nodes unique to List B (before intersection)
• c = shared nodes (from intersection to end)

Pointer A travels: a + c + b steps (A’s unique + shared + B’s unique) Pointer B travels: b + c + a steps (B’s unique + shared + A’s unique)

Both travel a + b + c steps total. Since they travel the same distance and the last c nodes are shared, they must meet at the intersection node.

If there is no intersection (c = 0), both reach None after a + b steps.

# Example:
# A: [A1, A2, A3, C1, C2]  a=3, c=2
# B: [B1, B2, C1, C2]      b=2, c=2
#
# pA path: A1→A2→A3→C1→C2→None→B1→B2→C1 (meets at C1, 8 steps)
# pB path: B1→B2→C1→C2→None→A1→A2→A3→C1 (meets at C1, 8 steps)

Building Test Cases

def build_intersection_lists(a_vals, b_vals, shared_vals):
    """
    Build two lists that share a common tail.
    Returns (headA, headB, intersection_node)
    """
    # Build shared tail
    shared_head = None
    shared_tail = None
    for val in shared_vals:
        node = ListNode(val)
        if not shared_head:
            shared_head = node
            shared_tail = node
        else:
            shared_tail.next = node
            shared_tail = node

    # Build list A
    dummyA = ListNode(0)
    curr = dummyA
    for val in a_vals:
        curr.next = ListNode(val)
        curr = curr.next
    curr.next = shared_head  # Connect to shared part

    # Build list B
    dummyB = ListNode(0)
    curr = dummyB
    for val in b_vals:
        curr.next = ListNode(val)
        curr = curr.next
    curr.next = shared_head  # Connect to shared part

    return dummyA.next, dummyB.next, shared_head


# Test case 1: Lists with intersection
headA, headB, expected = build_intersection_lists(
    a_vals=[1, 2, 3],
    b_vals=[4, 5],
    shared_vals=[6, 7, 8]
)

result = get_intersection_two_pointer(headA, headB)
print(f"Intersection value: {result.val}")  # 6
assert result is expected, "Should be the same node object"

# Test case 2: No intersection
headX = ListNode(1, ListNode(2, ListNode(3)))
headY = ListNode(4, ListNode(5))

result = get_intersection_two_pointer(headX, headY)
print(f"No intersection: {result}")  # None

# Test case 3: One list is empty
result = get_intersection_two_pointer(None, headY)
print(f"Empty list: {result}")  # None

# Test case 4: Same list
result = get_intersection_two_pointer(headX, headX)
print(f"Same list: {result.val}")  # 1 (head is intersection)

Edge Cases to Handle

def get_intersection_safe(headA, headB):
    """Handle all edge cases."""
    # Both empty
    if not headA or not headB:
        return None

    # Same head — they're the same list
    if headA is headB:
        return headA

    # Standard two-pointer
    pA, pB = headA, headB
    while pA is not pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA

    return pA

Edge Case	Result
Both lists empty	None
One list empty	None
No intersection	None
Same head node	Returns head
Intersection at last node	Returns last node
Equal length with intersection	Works normally
Very different lengths	Works normally

Verifying Intersection Exists

Sometimes you just need a boolean:

def lists_intersect(headA, headB):
    """
    Check if two lists share a common tail.
    Time: O(n + m), Space: O(1)
    """
    if not headA or not headB:
        return False

    # Find tails
    tailA = headA
    while tailA.next:
        tailA = tailA.next

    tailB = headB
    while tailB.next:
        tailB = tailB.next

    # If tails are the same node, lists intersect
    return tailA is tailB

This is faster than finding the exact intersection point when you only need a yes/no answer.

Why Intersection Matters

Memory Management

In languages like C/C++, if two data structures share a linked list tail, you need to know about the intersection to avoid:

• Double free: Freeing the shared nodes twice causes a crash
• Use after free: One structure frees the shared nodes while the other still uses them
• Memory leaks: Neither structure frees the shared nodes because each assumes the other will

Graph Representations

In directed graphs represented with adjacency lists, two paths may merge at a common node. Finding merge points helps with:

• Detecting shared substructures
• Optimizing traversals by avoiding redundant work
• Finding least common ancestors in tree-like structures

Git Merge Base

Git’s merge-base command finds the common ancestor of two branches — conceptually similar to finding where two linked lists of commits intersect.

Comparison of Approaches

Approach	Time	Space	Pros	Cons
Hash Set	O(n+m)	O(n)	Simple	Extra space
Length Difference	O(n+m)	O(1)	No extra space	Two passes
Two-Pointer	O(n+m)	O(1)	Elegant, one loop	Less intuitive
Tail Comparison	O(n+m)	O(1)	Only yes/no	No intersection node

Finding All Shared Nodes

Once you find the intersection point, you can enumerate all shared nodes:

def get_shared_nodes(headA, headB):
    """
    Return a list of all shared node values after the intersection.
    """
    intersection = get_intersection_two_pointer(headA, headB)
    if not intersection:
        return []

    shared = []
    current = intersection
    while current:
        shared.append(current.val)
        current = current.next
    return shared


headA, headB, _ = build_intersection_lists([1, 2], [3], [4, 5, 6])
print(get_shared_nodes(headA, headB))  # [4, 5, 6]

Disconnecting Intersecting Lists

Sometimes you need to separate two intersecting lists:

def disconnect_lists(headA, headB):
    """
    If lists intersect, disconnect them so each has its own tail.
    Returns (headA, headB) — headB's tail becomes None.
    """
    intersection = get_intersection_two_pointer(headA, headB)
    if not intersection:
        return headA, headB  # Already separate

    # Find the node in list B just before the intersection
    if headB is intersection:
        # B starts at intersection — just return B as None
        return headA, None

    prev = headB
    while prev.next is not intersection:
        prev = prev.next

    prev.next = None  # Disconnect B from shared tail
    return headA, headB

Complexity Summary

Operation	Time	Space
Two-pointer intersection	O(n + m)	O(1)
Hash set intersection	O(n + m)	O(n)
Length difference method	O(n + m)	O(1)
Check if intersecting	O(n + m)	O(1)

Practice Problems

1. LeetCode 160 — Intersection of Two Linked Lists: The classic problem (Easy)
2. LeetCode 141 — Linked List Cycle: Related two-pointer technique (Easy)
3. LeetCode 142 — Linked List Cycle II: Find the cycle start (Medium)
4. LeetCode 1650 — Lowest Common Ancestor of a Binary Tree III: Similar merge-point concept with parent pointers (Medium)
5. Git merge-base: Real-world application of finding common ancestors

Key Takeaways

• Linked list intersection means shared physical nodes, not just equal values.
• The two-pointer technique is the most elegant solution: redirect each pointer to the other list’s head when it reaches None. Both travel a + b + c steps and meet at the intersection.
• The technique works because the total distance is equalized by the cross-redirection.
• Always check edge cases: empty lists, no intersection, same list, intersection at the head.
• Intersection detection is fundamental in memory management, garbage collection, and version control systems.