Determining the intersection point of two lists in O(1) space
This was meant to be a single post outlining an approach for determining the intersection of two singly-linked lists in constant space and its generalisation, but it grew too large. I’ll publish the first part covering the linked list algorithm here, and I’ll leave the generalisation for next time.
A while back a friend shared this problem with me. Given the heads of two singly-linked lists, it asks for an algorithm to find the node at which they intersect. We can assume the input lists don’t have cycles. The problem also requires the linked lists to retain their structure after the algorithm is finished. To make things more interesting my friend also asked if this can be done in O(1) space. This rules out the obvious O(n) space solution where we store the first list’s nodes in a hash table and check if any of the nodes in the second list are present in it.
If the lists were the same length this would be easy to solve in constant space: just walk over the two lists at the same time and compare the elements. Since our lists can be any length we can’t use this approach.
