Solving Intersection of Two Linked Lists in Python: Step-by-Step Guide

Introduction to the Intersection of Two Linked Lists Problem

The "Intersection of Two Linked Lists" is a classic algorithmic problem frequently encountered in coding interviews and competitive programming. Given the heads of two singly linked lists, your task is to determine the node at which the two lists intersect. If they do not intersect, you should return null (or None in Python).

What makes this problem particularly interesting is the constraint that the two lists may have different lengths before the intersection point. The intersection is defined by reference equality — meaning both lists share the exact same node in memory, not just nodes with equal values. This subtle distinction is crucial for understanding the problem correctly.

Why This Problem Matters

Interview Relevance: It is a staple question on platforms like LeetCode and in technical interviews at major tech companies.
Pointer Manipulation: It tests your understanding of linked list traversal and pointer arithmetic.
Algorithmic Thinking: It encourages finding optimal solutions beyond the brute-force approach.
Real-World Parallels: The concept of merging paths appears in version control systems, network routing, and memory management.

Understanding the Problem Statement

Consider two linked lists that eventually merge into a single shared tail. Before the merge point, each list may have a different number of nodes. After the merge point, both lists share the same sequence of nodes.

For example, given list A: 4 -> 1 -> 8 -> 4 -> 5 and list B: 5 -> 6 -> 1 -> 8 -> 4 -> 5, the intersection occurs at the node with value 8. From that node onward, both lists share the same nodes.

Key constraints typically include:

The lists must not contain any cycles.
You should aim for O(n) time complexity and O(1) memory complexity.
You cannot modify the input lists.

Setting Up the Linked List Data Structure

Before solving the problem, we need a basic singly linked list node class in Python. This class will serve as the foundation for all subsequent solutions.

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

    def __repr__(self):
        return f"ListNode({self.val})"


def build_intersecting_lists(list_a_vals, list_b_vals, intersect_vals):
    """Helper to construct two lists that share a common tail."""
    if not intersect_vals:
        return build_simple_list(list_a_vals), build_simple_list(list_b_vals), None

    # Build the shared tail
    intersect_head = ListNode(intersect_vals[0])
    current = intersect_head
    for val in intersect_vals[1:]:
        current.next = ListNode(val)
        current = current.next

    # Build list A and attach the shared tail
    head_a = ListNode(list_a_vals[0]) if list_a_vals else intersect_head
    current = head_a
    for val in list_a_vals[1:]:
        current.next = ListNode(val)
        current = current.next
    if list_a_vals:
        current.next = intersect_head

    # Build list B and attach the shared tail
    head_b = ListNode(list_b_vals[0]) if list_b_vals else intersect_head
    current = head_b
    for val in list_b_vals[1:]:
        current.next = ListNode(val)
        current = current.next
    if list_b_vals:
        current.next = intersect_head

    return head_a, head_b, intersect_head


def build_simple_list(values):
    """Build a simple linked list from a list of values."""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

This setup allows us to create test cases where two lists genuinely share the same nodes in memory, which is essential for validating our solutions.

Approach 1: Brute Force

The most straightforward approach is to compare every node of list A with every node of list B. When we find a matching reference, we return it. While simple to implement, this approach has significant performance drawbacks.

def get_intersection_node_brute_force(head_a, head_b):
    """O(m * n) time, O(1) space."""
    current_a = head_a
    while current_a:
        current_b = head_b
        while current_b:
            if current_a is current_b:
                return current_a
            current_b = current_b.next
        current_a = current_a.next
    return None

This solution has a time complexity of O(m × n), where m and n are the lengths of the two lists. For large lists, this becomes prohibitively slow. The space complexity is O(1), which is its only redeeming quality.

Approach 2: Hash Set for Seen Nodes

A more efficient approach uses a hash set to store references to all nodes in one list, then traverses the second list checking for membership. This trades memory for speed.

def get_intersection_node_hashset(head_a, head_b):
    """O(m + n) time, O(m) space."""
    seen = set()
    current = head_a
    while current:
        seen.add(current)
        current = current.next

    current = head_b
    while current:
        if current in seen:
            return current
        current = current.next
    return None

This approach runs in O(m + n) time, a significant improvement over brute force. However, it requires O(m) additional space to store the nodes of the first list. While acceptable in many scenarios, interviewers often push for a solution with O(1) space complexity.

Approach 3: Length Difference Alignment

This approach eliminates the extra space by first calculating the lengths of both lists. We then advance the pointer of the longer list by the difference in lengths, so both pointers are equidistant from the potential intersection point. Finally, we traverse both lists simultaneously until the pointers meet.

def get_length(head):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    return length


def get_intersection_node_length(head_a, head_b):
    """O(m + n) time, O(1) space."""
    len_a = get_length(head_a)
    len_b = get_length(head_b)

    current_a = head_a
    current_b = head_b

    # Advance the longer list's pointer
    diff = abs(len_a - len_b)
    if len_a > len_b:
        for _ in range(diff):
            current_a = current_a.next
    else:
        for _ in range(diff):
            current_b = current_b.next

    # Traverse both lists in tandem
    while current_a and current_b:
        if current_a is current_b:
            return current_a
        current_a = current_a.next
        current_b = current_b.next

    return None

This solution achieves O(m + n) time complexity and O(1) space complexity, making it an excellent answer for interviews. The logic is clear and easy to explain, which is a significant advantage when communicating your thought process.

Approach 4: Two-Pointer Technique (Optimal)

The two-pointer technique is the most elegant solution. The idea is to use two pointers, one for each list. When a pointer reaches the end of its list, it switches to the head of the other list. If the lists intersect, the pointers will meet at the intersection node after at most two passes. If they do not intersect, both pointers will reach None simultaneously.

def get_intersection_node(head_a, head_b):
    """O(m + n) time, O(1) space. Elegant two-pointer approach."""
    if not head_a or not head_b:
        return None

    pointer_a = head_a
    pointer_b = head_b

    while pointer_a is not pointer_b:
        # When reaching the end of one list, switch to the other's head
        pointer_a = pointer_a.next if pointer_a else head_b
        pointer_b = pointer_b.next if pointer_b else head_a

    return pointer_a

Why This Works

The magic of this approach lies in the equalization of traversal distances. Suppose list A has length a + c and list B has length b + c, where c is the length of the shared tail. Pointer A traverses a + c nodes, then switches to list B and traverses b more nodes, for a total of a + c + b steps. Pointer B traverses b + c nodes, then switches to list A and traverses a more nodes, for a total of b + c + a steps. Both pointers travel the same total distance, so they meet at the intersection node.

If there is no intersection, both pointers traverse a + b nodes total and reach None at the same time, causing the loop to terminate gracefully.

Testing the Solutions

Let us verify our solutions with comprehensive test cases, including edge cases such as no intersection, intersection at the head, and lists of unequal lengths.

def test_intersection():
    # Test 1: Lists intersect in the middle
    head_a, head_b, expected = build_intersecting_lists(
        list_a_vals=[4, 1],
        list_b_vals=[5, 6, 1],
        intersect_vals=[8, 4, 5]
    )
    result = get_intersection_node(head_a, head_b)
    assert result is expected, f"Test 1 failed: expected {expected}, got {result}"
    print("Test 1 passed: Intersection found at", result)

    # Test 2: No intersection
    head_a = build_simple_list([2, 6, 4])
    head_b = build_simple_list([1, 5])
    result = get_intersection_node(head_a, head_b)
    assert result is None, f"Test 2 failed: expected None, got {result}"
    print("Test 2 passed: No intersection (None)")

    # Test 3: Intersection at the head
    shared = ListNode(1)
    shared.next = ListNode(2)
    head_a = shared
    head_b = shared
    result = get_intersection_node(head_a, head_b)
    assert result is shared, f"Test 3 failed: expected {shared}, got {result}"
    print("Test 3 passed: Intersection at head")

    # Test 4: One list is a subset of the other
    head_a, head_b, expected = build_intersecting_lists(
        list_a_vals=[1, 2, 3],
        list_b_vals=[],
        intersect_vals=[4, 5, 6]
    )
    result = get_intersection_node(head_a, head_b)
    assert result is expected, f"Test 4 failed: expected {expected}, got {result}"
    print("Test 4 passed: List B starts at intersection")

    # Test 5: Both lists are empty
    result = get_intersection_node(None, None)
    assert result is None, f"Test 5 failed: expected None, got {result}"
    print("Test 5 passed: Both lists empty")

    print("\nAll tests passed!")


if __name__ == "__main__":
    test_intersection()

Running this test suite confirms that the two-pointer solution handles all edge cases correctly. You can replace get_intersection_node with any of the other implementations to verify their correctness as well.

Best Practices and Common Pitfalls

Best Practices

Use reference equality: Always compare nodes with is rather than ==, since two different nodes can have the same value.
Handle edge cases: Always check for empty lists at the beginning of your function.
Avoid modifying input: Do not alter the structure of the input lists, as this can cause side effects in the calling code.
Prefer the two-pointer approach: It is concise, efficient, and demonstrates a deep understanding of the problem.
Write clear helper functions: Functions like get_length improve readability and reusability.

Common Pitfalls

Confusing value equality with reference equality: Using == instead of is will produce false positives when nodes have identical values but are different objects.
Infinite loops: A faulty two-pointer implementation can loop forever if the termination condition is not handled correctly. Ensure that both pointers can reach None.
Forgetting the no-intersection case: Your solution must return None when the lists do not intersect, not raise an exception.
Off-by-one errors in length alignment: When using the length-difference approach, be careful to advance the correct pointer by the correct number of steps.

Performance Comparison

Here is a summary of the time and space complexities for each approach discussed:

Brute Force: O(m × n) time, O(1) space — simple but slow.
Hash Set: O(m + n) time, O(m) space — fast but uses extra memory.
Length Alignment: O(m + n) time, O(1) space — efficient and intuitive.
Two-Pointer: O(m + n) time, O(1) space — optimal and elegant.

In practice, the two-pointer technique is the recommended solution because it achieves the best possible time and space complexity while remaining concise and easy to implement. The length-alignment approach is a strong alternative if you find the two-pointer logic difficult to explain or remember.

Conclusion

Solving the intersection of two linked lists problem is a valuable exercise in algorithmic thinking and pointer manipulation. We explored four approaches, progressing from a naive brute-force method to the elegant two-pointer technique that achieves optimal O(m + n) time and O(1) space complexity. The key insight is that by switching pointers between lists, both traverse the same total distance and are guaranteed to meet at the intersection point if one exists. Mastering this problem not only prepares you for technical interviews but also deepens your understanding of linked list operations and memory references in Python. Practice implementing each approach, test against edge cases, and internalize the reasoning behind the two-pointer method — it is a pattern that appears in many other linked list problems as well.