algorithm - Check if two linked lists merge. If so, where?

Question

This question may be old, but I couldn't think of an answer.

Say, there are two lists of different lengths, merging at a point; how do we know where the merging point is?

Conditions:

1. We don't know the length
2. We should parse each list only once.

Answer 1

The following is by far the greatest of all I have seen - O(N), no counters. I got it during an interview to a candidate S.N. at VisionMap.

Make an interating pointer like this: it goes forward every time till the end, and then jumps to the beginning of the opposite list, and so on. Create two of these, pointing to two heads. Advance each of the pointers by 1 every time, until they meet. This will happen after either one or two passes.

I still use this question in the interviews - but to see how long it takes someone to understand why this solution works.