Find the middle node of a Linked List

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

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

Recommended reading

Author
Amin Ariana
Published
May 2007