Cracking The Coding Interview Together – Problem 2.7: Intersection

If you’ve been following the series, you already know the drill. We don’t rush to code. We don’t jump straight to clever tricks. We slow down, understand what the problem is really asking, and then work our way toward a solution the same way you would in an actual interview.

Today’s problem looks innocent at first glance. Two linked lists. Find where they intersect. Simple, right?

Not quite.

This is one of those questions where many candidates get tripped up—not because the logic is complex, but because they misunderstand the definition of intersection. Let’s fix that together.

Let’s get into it.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Intersection
Given two singly linked lists, determine if the two lists intersect. Return the intersecting node.

Note that the intersection is defined based on reference, not value.
That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

Analyse the problem statement together

Let’s break it down slowly.

You’re given two linked lists. At some point, they might merge and continue as a shared tail.

Something like this:

List A: a → b → c → d
                     ↘
                       f → g
                     ↗
List B: x → y → z

From node f onward, both lists are literally pointing to the same nodes in memory.

This is the key idea:

• Intersection is not about having the same values
• Intersection is about sharing the same node reference

Two nodes with value 5 are not intersecting if they are different objects.

Questions for the interviewer

Before touching a keyboard, pause here. This is where good candidates stand out.

Here are the questions I would ask the interviewer:

1. Can the two lists be of different lengths?
2. Can one or both lists be empty?
3. Are the lists guaranteed to be singly linked?
4. Is there at most one intersection point?
5. Should we return the node itself or just indicate whether an intersection exists?

Most interviewers will clarify something like:

• Yes, lists can be of different lengths
• Yes, lists can be empty
• Yes, singly linked lists
• There will be at most one intersection point
• Return the intersecting node (or null if there isn’t one)

These clarifications matter. Don’t skip this step.

Think about the Solution

I’ll say this again, because it’s important.

Before reading further, stop for a minute.

Ask yourself:

• How would I explain this to someone else?
• What property of intersecting lists can I exploit?
• What stays the same even if the list lengths are different?

This is exactly what an interviewer wants to see: how you think when you don’t have the answer immediately.

Think Out Loud: How Would You Approach This?

Let’s reason from first principles.

If two linked lists intersect, what must be true?

Key Observation #1: The tails must be the same

If two lists share nodes at the end, then their last node must be the same reference.

If the last nodes are different objects, the lists cannot intersect. Period.

That gives us an early exit condition.

Key Observation #2: Length matters, but only initially

The two lists might have different lengths before they intersect.

If we could:

1. Measure the lengths
2. Skip nodes in the longer list
3. Then move both pointers together

Eventually, they would either:

• Meet at the intersection node, or
• Reach the end together without meeting

This idea should already feel promising.

A Naive (Brute Force) Approach

Let’s acknowledge the brute-force solution first.

Brute Force Idea

For each node in list A:

• Traverse list B and check if any node is the same reference

Why This Is Bad

• Time complexity: O(n × m)
• Space complexity: O(1)

Yes, it works.
No, you should not lead with this in an interview.

But it’s worth mentioning briefly, because it shows you considered simpler options and rejected them for good reasons.

A Better Approach Using a Hash Set

Another common approach is to use extra memory.

Idea

1. Traverse list A and store each node reference in a HashSet
2. Traverse list B and check if any node already exists in the set

Complexity

• Time: O(n + m)
• Space: O(n)

This is acceptable, but most interviewers will follow up with:

“Can you do it without extra space?”

So let’s go one step further.

The Optimal Solution (No Extra Space)

This is the solution interviewers really want to see.

High-Level Steps

1. Traverse both lists to get their lengths
2. Get the tail nodes and compare them
   • If tails differ → no intersection
3. Advance the pointer of the longer list by the difference in lengths
4. Move both pointers one step at a time
5. The first node where they match by reference is the intersection

This approach is elegant, efficient, and grounded in reasoning.

Write code and explain

Now let’s translate this idea into code.

Java code

Node Definition (Assumed)

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

Helper Class to Store Tail and Size

class Result {
    ListNode tail;
    int size;

    Result(ListNode tail, int size) {
        this.tail = tail;
        this.size = size;
    }
}

Step 1: Get Tail and Size

private static Result getTailAndSize(ListNode head) {
    if (head == null) return null;

    int size = 1;
    ListNode current = head;

    while (current.next != null) {
        size++;
        current = current.next;
    }

    return new Result(current, size);
}

Step 2: Advance Pointer by K Steps

private static ListNode advanceByK(ListNode node, int k) {
    while (k > 0 && node != null) {
        node = node.next;
        k--;
    }
    return node;
}

Step 3: Main Intersection Logic

public static ListNode findIntersection(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;

    Result resultA = getTailAndSize(headA);
    Result resultB = getTailAndSize(headB);

    // If tails are not the same, there is no intersection
    if (resultA.tail != resultB.tail) {
        return null;
    }

    // Set pointers to the start of each list
    ListNode shorter = resultA.size < resultB.size ? headA : headB;
    ListNode longer = resultA.size < resultB.size ? headB : headA;

    // Advance the pointer for the longer list
    longer = advanceByK(longer, Math.abs(resultA.size - resultB.size));

    // Move both pointers until they collide
    while (shorter != longer) {
        shorter = shorter.next;
        longer = longer.next;
    }

    return shorter; // or longer, same thing
}

Why This Works

Once both pointers are aligned at the same distance from the tail:

• Every step forward keeps them in sync
• If there is an intersection, they will collide at the exact node
• If not, they reach the end together

No guessing. No hacks. Just logic.

Time & Space Complexity

Let’s be explicit — interviewers care about this.

• Time Complexity:
  O(n + m)
  We traverse each list a constant number of times.
• Space Complexity:
  O(1)
  No additional data structures used.

This is optimal.

Final Thoughts

This problem isn’t really about linked lists.

It’s about:

• Understanding references vs values
• Reasoning about structure, not data
• Explaining your approach calmly and clearly

If you can walk an interviewer through this solution—step by step, the way we just did—you’re not just solving the problem. You’re demonstrating that you think like an engineer.

In the next post, we’ll continue building on these ideas and tackle another linked list problem that looks simple but hides a subtle twist.

Until then — take your time, revisit the code, and try explaining it out loud to yourself.

That’s where the real learning happens.

Happy coding 👋