Intersecting Linked Lists Faster  posted by Craig Gidney on
March 26, 2013  Yesterday, I read the post “Of intersecting
linked lists” by one Paul Masurel. In it, he discusses the
problem of determining the first node that is common to two
linked lists. He ends with a solution that takes O(d) time and
O(\log{d}) space, where d is the maximum distance to the first
common node from the head of either list. I would inline the
solution here, but it’s fifty lines of carefully chosen branches
(euphemism: “branch noise”).  There is actually a solution much
simpler than Paul’s. One just as time efficient, but requiring
only constant space.  From n to d  The comments about the post
on reddit almost came up with the right algorithm. People
realized that if you computed the lists’ lengths then you could
line up the heads so they advanced to the common node in sync.
This removes the need for any sort of collection of seen nodes,
reducing the space requirements to constant.  The problem is
that computing the lengths of the