[Java] Find intersection of singly linked lists

Given two singly linked lists that might have a node in common, find that node without altering the lists and using constant space.

If we could alter the nodes in the list, we could flag visited ones and do a O(M) followed by an O(N) walk, when we find an already visited node, that is the common node.

An alternative could be to link the tail of a list to the head, then use a cycle detection algorithm to find the start of the cycle which will be the common node.

But without touching the lists or nodes we are limited in our options. One thing we can do is walk both lists once to find their lengths, then walk down the longer list until we reach same length as the other, finally walk down both lists at the same time until we find a common node.

All these approaches have O(M+N) time and O(1) space.

You can check my implementation of findIntersection on my Gist along with some tests in FindIntersectionJTests.