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

Time Complexity: Intersection Point of Two Linked Lists

O(m + n)

Understanding Time Complexity

We want to find where two linked lists meet, if at all. Understanding how long this takes helps us write efficient code.

How does the time needed grow as the lists get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find intersection node of two singly linked lists
struct Node* getIntersectionNode(struct Node* headA, struct Node* headB) {
    struct Node *a = headA, *b = headB;
    while (a != b) {
        a = (a == NULL) ? headB : a->next;
        b = (b == NULL) ? headA : b->next;
    }
    return a;
}
    

This code tries to find the node where two linked lists intersect by traversing both lists with two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing nodes of both linked lists using two pointers.
• How many times: Each pointer moves through its list and then switches to the other list once, repeating until they meet or both reach the end.

How Execution Grows With Input

As the lists get longer, the pointers travel through each node at most twice before meeting or ending.

Input Size (n)	Approx. Operations
10	About 20 steps (each pointer traverses both lists)
100	About 200 steps
1000	About 2000 steps

Pattern observation: The total steps grow roughly linearly with the sum of the lengths of both lists.

Final Time Complexity

Time Complexity: O(m + n)

This means the time grows linearly with the total number of nodes in both lists combined.

Common Mistake

[X] Wrong: "The pointers only traverse one list each, so time is O(max(m, n))"

[OK] Correct: Each pointer may traverse both lists once, so total steps depend on the sum of lengths, not just the longer list.

Interview Connect

Understanding this approach shows you can handle linked list problems efficiently by clever pointer use, a skill valued in many coding challenges.

Self-Check

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