DSA: The Linked List Intersection Solution I Wish I Had Thought Of

Lately, I've been practicing my Data Structures and Algorithms (DSA) skills by solving LeetCode problems and studying the book Coding Interview Patterns.

One thing I like to do when reading this book is to try solving each problem before reading the author's intuition or solution. I want to see what I can come up with on my own first.

Recently, I came across the Linked List Intersection problem, which is the same as LeetCode #160 — Intersection of Two Linked Lists.

This wasn't my first time solving this problem. I had already worked on it back in 2019, when I was getting into DSA, so I had an idea of how to approach it.

I ended up implementing two solutions before reading the book's explanation. The second one was already optimal in terms of time and space complexity.

However, I was impressed when I saw the solution explained in the book. I understood it almost immediately because it was a variation of my second approach, but I hadn't thought about solving the problem that way.

It made me wonder: How did someone even come up with this?

The problem

We're given two singly linked lists, and we need to find the node where they intersect.

For example:

Both lists share the same nodes starting at c1. We're looking for the same node in memory, not just two nodes containing the same value.

For the following implementations, I'm using these Go structures:

type Node struct {
    Value int
    Next  *Node
}

type LinkedList struct {
    Head *Node
}

My first approach: a hash set

As I mentioned, I had already solved this problem in 2019, and that's where my first intuition came from.

If you have basic knowledge of data structures like hash sets and linked lists, this is a pretty straightforward approach. You can probably come up with it in a few minutes.

The idea is to traverse the first list (it can also be the second one) and store its nodes in a hash set. Then traverse the second list and check whether each node exists in the set.

Here's my implementation:

func findLinkedListIntersectionNaiveSolution(l1 LinkedList, l2 LinkedList) *Node {
    // hash set to store the seen nodes
    hs := make(map[*Node]struct{})

    // traverse l1 and store all its nodes
    ptr := l1.Head
    for ptr != nil {
        hs[ptr] = struct{}{}
        ptr = ptr.Next
    }

    // traverse l2 looking for a node we've already seen
    ptr = l2.Head
    for ptr != nil {
        if _, ok := hs[ptr]; ok {
            return ptr
        }
        ptr = ptr.Next
    }

    return nil
}

The complexity of this solution is easy to deduce. Let's assume n and m are the lengths of the first and second lists, respectively. Given that, we have:

• Time complexity: O(n + m) because we need to traverse both lists in the worst case.
• Space complexity: O(n) since the memory grows as the input grows.

The time complexity is already good enough, but I thought the space complexity could be improved. I wanted to avoid storing all those nodes in memory just to find the intersection. So I started thinking about using only pointers.

My second approach: aligning the pointers

My next idea was to traverse both lists at the same time and compare their nodes.

The problem is that the lists can have different lengths. If both pointers start at their respective heads and advance together, they might reach the intersection at different moments.

For example:

The first pointer needs to traverse three nodes before reaching c1, while the second only needs to traverse one.

I thought about calculating the lengths of both lists and using the difference as an offset. I could advance the pointer of the longer list by that amount, then move both pointers together until they reached the same node.

That's how I came up with this solution:

func findLinkedListIntersectionNaiveSolution2(l1 LinkedList, l2 LinkedList) *Node {
    ptr1, ptr2 := l1.Head, l2.Head
    var lenL1, lenL2 int

    // calculate the length of both lists
    for ptr1 != nil || ptr2 != nil {
        if ptr1 != nil {
            ptr1 = ptr1.Next
            lenL1++
        }

        if ptr2 != nil {
            ptr2 = ptr2.Next
            lenL2++
        }
    }

    // calculate the difference between their lengths
    diff := lenL1 - lenL2
    k := max(diff, -diff)

    // Set ptr1 to the longer list.
    if lenL2 > lenL1 {
        ptr1, ptr2 = l2.Head, l1.Head
    } else {
        ptr1, ptr2 = l1.Head, l2.Head
    }

    // align the pointers and find the intersection
    for ptr1 != ptr2 {
        if k > 0 {
            ptr1 = ptr1.Next
            k--
            continue
        }

        ptr1, ptr2 = ptr1.Next, ptr2.Next
    }

    return ptr1
}

This worked, and I managed to reduce the space complexity to O(1) while keeping the time complexity at O(n + m).

I was happy with this approach. The reasoning made sense to me: if the pointers have different distances to the end, I can calculate that difference and compensate for it.

At this point, I had an optimal solution, so I continued reading the book.

The solution that surprised me

The book started by pointing out something simple: if two linked lists have the same length, finding their intersection is easier. We can traverse both lists simultaneously, and since they have the same number of nodes remaining, both pointers will reach the intersection at the same time.

But what if the lists have different lengths?

The book proposed an interesting way to think about this. Instead of treating A and B as two separate lists, imagine combining them into two longer lists:

Even if A and B have different lengths, these two combined lists will always have the same length. And if the original lists intersect, both combined traversals also share the same tail nodes.

So now we have two lists of equal length, which is exactly the condition that makes it possible to find the intersection by advancing both pointers simultaneously.

This was me after getting it:

The interesting part is that we don't actually need to connect or modify any nodes. We can simulate these combined lists by traversing A and switching to the head of B when we reach the end of the list, and doing the opposite with the other pointer.

Here's my implementation:

func findLinkedListIntersectionGodLikeImplementation(l1 LinkedList, l2 LinkedList) *Node {
    ptr1 := l1.Head
    ptr2 := l2.Head

    for ptr1 != ptr2 {
        if ptr1 != nil {
            ptr1 = ptr1.Next
        } else {
            ptr1 = l2.Head
        }

        if ptr2 != nil {
            ptr2 = ptr2.Next
        } else {
            ptr2 = l1.Head
        }
    }

    return ptr1
}

It has the same complexity as my second solution:

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

What impressed me was the reasoning behind it. The book starts with the easiest version of the problem, where both lists have equal lengths, and then finds a way to turn the original problem into that version.

I understood it because it was closely related to my second approach, but I hadn't considered combining the traversals.

I think what makes it work is that the problem is transformed into its simplest form.

The math behind the solution: why is that true?

Let's use our original example:

We can divide both lists into three sections:

• a: the number of nodes exclusive to List A.
• b: the number of nodes exclusive to List B.
• c: the number of nodes shared by both lists.

Their lengths are:

Length(A) = a + c
Length(B) = b + c

Now consider the two combined traversals:

Assuming the pointers don't meet during their first traversal, let's calculate how many steps each one takes to reach the intersection.

For the first pointer:

Traverse List A:               a + c
Reach the intersection in B:   b

Total = a + c + b

For the second pointer:

Traverse List B:               b + c
Reach the intersection in A:   a

Total = b + c + a

Both pointers travel exactly the same distance:

a + c + b = b + c + a

This follows from the commutative property of addition:

a + b = b + a

Each pointer traverses the exclusive portion of both lists and the shared portion once before reaching the intersection on its second traversal. Since they move one node at a time, they arrive at the intersection simultaneously.

If a = b, they can meet during the first traversal. If the lists don't intersect, both pointers eventually reach the end of the list together after traversing both lists.

My second solution was calculating the difference between the lengths and adjusting one pointer. This approach compensates for that difference automatically.

And that's what I found so interesting. I could understand the mathematics behind it, but I don't think I would have considered switching the pointers to the opposite lists.

How did someone come up with this?

After reading the solution, I became curious about its origin.

Was it inspired by another algorithm? Was there some mathematical reasoning that led someone to it? Or did someone simply notice that switching the pointers would make their distances equal?

I started looking around the internet and discussing the problem with ChatGPT to see what I could find. I've been practicing DSA since 2019, but there's probably a lot of context and older discussions I've missed.

On October 20, 2009, someone posted a question on Stack Overflow titled Check if two linked lists merge. If so, where?. It's essentially the same problem as LeetCode #160.

This doesn't tell us when the problem was first introduced, but at least we know it was already being discussed publicly in 2009.

On February 19, 2013, someone called Pavel Radzivilovsky posted an answer to that Stack Overflow question. He described the pointer-switching technique and mentioned learning it from a candidate, during an interview.

I found this particularly interesting because the interviewer learned the technique from the candidate. It also made me more curious about how that candidate knew the solution. Maybe they had seen it before, or maybe they came up with it independently. Unfortunately, the answer doesn't explain that part.

I also found a blog post from December 2014 explaining the same technique and referring to LeetCode.

There were also published solutions in 2015 discussing the problem.

An archived version of the LeetCode problem statement credits user @stellari for contributing the problem and its test cases. That doesn't necessarily mean they invented the pointer-switching approach, though.

The 2013 Stack Overflow answer is one of the earliest documented references to the technique that I could find. But I couldn't establish its actual origin. It might be older than those references.

I couldn't find an accurate origin for this technique, and I'm still curious about how someone discovered it. Maybe they started with the length-alignment approach, as I did, and noticed that switching the pointers would have the same effect without calculating anything. I don't know.

Final thoughts

What I liked most about this problem was comparing my own reasoning with the solution from the book.

My second approach was already optimal, so I wasn't expecting a major difference in the solution. But I hadn't considered that both pointers could simply switch lists and end up covering the same distance.

After looking at the math, it makes perfect sense. It's just the commutative property of addition applied to the lengths of two linked lists.

One thing I learned from this is: understanding why an algorithm works and coming up with it yourself are two different levels of understanding of the problem and how to approach it.

I still don't know who originally came up with this technique, but whoever it was, that solution was a little too clever for me.