Intersection Point of Two Linked Lists in DSA Python - Time & Space Complexity

Time Complexity: Intersection Point of Two Linked Lists

O(n + m)

Understanding Time Complexity

We want to understand how long it takes to find where two linked lists meet.

How does the time grow as the lists get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def get_intersection_node(headA, headB):
    ptrA, ptrB = headA, headB
    while ptrA != ptrB:
        ptrA = ptrA.next if ptrA else headB
        ptrB = ptrB.next if ptrB else headA
    return ptrA
    

This code finds the node where two linked lists first meet or returns None if they don't intersect.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving pointers forward through each list node.
• How many times: Each pointer moves at most twice the length of the longer list.

How Execution Grows With Input

As the lists get longer, the pointers move through each node, then switch to the other list once.

Input Size (n)	Approx. Operations
10	About 20 pointer moves
100	About 200 pointer moves
1000	About 2000 pointer moves

Pattern observation: The number of steps grows roughly twice as fast as the length of the longer list.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the total length of both lists combined.

Common Mistake

[X] Wrong: "The pointers only move once through each list, so it’s O(n)."

[OK] Correct: Each pointer can traverse both lists once, so the total steps add up to the sum of both list lengths, not just one.

Interview Connect

Understanding this time complexity helps you explain how efficient your solution is when lists get large, showing you can reason about real-world data sizes.

Self-Check

"What if we used a hash set to store visited nodes from one list? How would the time complexity change?"