Problem 🤔

Given two (singly) linked lists, determine if the two lists intersect. Return the inter-secting 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.

Real World Applications 🌎

This is a great util function to apply to a linked list data structure to confirm we have no loops in our linked list.

The Finer Details 🔎

Let’s start with a naive approach. Assuming a valid linked list, with no loops has only unique values, we can traverse the list and look for duplicates. An easy way to do this is to keep track of all seen nodes in a set.

Solution 💡 - Brute Force

Complexity Analysis 🧮

Time complexity

O(n)

Loop over input with nested for loops.

Space complexity

O(n)

Constant amount of auxillary variables used.

This works! But can we do better? Do we really need O(n) space?!

Solution 💡 - Optimal

Explain Floyd’s Cycle Detection Algorithm. Here is a great video about it here.

Complexity Analysis 🧮

Time complexity

O(n)

Loop over input once

Space complexity

O(1)

Constant amount of auxillary variables used.

Resources 📚 💻

Cracking the Coding Interview (CTCI) 2.7