Intersection of Two Linked Lists — My First Working Approach

#dsa #beginners #cpp #programming

When I first solved LeetCode 160: Intersection of Two Linked Lists, I focused on understanding what “intersection” actually means.

This article explains:

how I approached the problem
why my solution works
what other (more optimal) approaches exist

Problem Understanding

You are given the heads of two singly linked lists.

Your task:

Return the node where the two linked lists intersect.
If they do not intersect, return null.

Important clarification

Intersection means same node in memory not same value.So comparison must be:

nodeA == nodeB

not

nodeA->val == nodeB->val.

My Approach: Brute Force Pointer Comparison

Idea

Traverse every node in list A for each node in A, traverse all nodes in list B.If both pointers point to the same node → intersection found

C++ Code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *i;
        ListNode *j;

        for (i = headA; i != NULL; i = i->next) {
            for (j = headB; j != NULL; j = j->next) {
                if (i == j)
                    return i; // intersection found
            }
        }
        return NULL; // no intersection
    }
};

Why This Works

Every possible pair of nodes is checked
Pointer comparison ensures we detect actual shared nodes
The moment two pointers match, we return that node
This guarantees correctness.

Complexity Analysis

Time Complexity O(n × m)
Space Complexity O(1)

✔️ Correct solution
❌ Not optimal due to nested loops

Other Approaches Exist (Just Awareness)

After solving this, I learned that there are better approaches:

Two pointer switching technique (most optimal)
Hashing using unordered_set
Length difference alignment method
These reduce time complexity to O(n + m).

But at this stage, my goal was. First solve correctly, then optimize.