Find the middle node of a Linked List

Problem Statement

Given a Singly Linked List, write an algorithm to find the middle node. You may not use more than one loop of any kind.

Evaluation

• Completeness of the C# or pseudo-code algorithm (25%)


• Correctness of the algorithm, demonstrated by quick manual unit tests (25%)


• What is the time and space complexity, and is it efficient? (25%)


• Modify it to find the node that is 3/4 of the way down instead of 1/2? (25%)

References

I was asked this question during a Microsoft interview