Q:

Algorithm to Find the pointer to the Node M Steps to Tail in a Singly Linked List

Suppose there is a singly linked list whose length is unknown. We want to find the node with M steps to the tail.
For example, the singly list is like this:
(A)->(B)->(C)->(X)->(Y)
and M = 2.
Then the output should be pointer to (C).
When confronting this quiz, my first reaction is to traverse the singly linked list to get the length N. Then traverse the singly the second time, but only forward N-M-1 steps. The time complexity is O(n) and space complexity is O(1).
Then, I'm challenged to find a solution to do it in one-traverse way. The solution is to have two pointers. The second pointer is M steps behind the first pointer. These two pointers move forward at same pace. When the first pointer reaches tail, the second pointer is the result.
After deep reflection on this question, I really don't believe the second "tricky" solution is superior than the first one. It is one-traverse, but it also involves 2*N-M pointer assignments. 
Any thought about this question?
Is there any other solution that is really faster?

A:

You should use a circular buffer
Allocate an array of M + 1 pointers, and fill in the (i mod M + 1)th pointer for each node through the list. When you reach the end, look M back in the array (wrapping around if you need to).
That way, you only have N writes!
Here's a hack job sample program in c++
node* get_Mth_from_end(node* head, int m)
{
  int pos = 0;
  node** node_array = new node*[m + 1];
  node_array[0] = head;
  while (node_array[(pos + 1) % (m + 1)] = node_array[pos % (m + 1)]->next)
     pos++;
  if (pos < m)
  {
     delete[] node_array;
     return NULL;
  }
  pos = pos - m;
  if (pos < 0)
     pos = pos + m + 1;
  node* retval = node_array[pos];
  delete[] node_array;
  return retval;
}

This should be checked for off by 1 errors.
My pointer syntax may be a little off too, but the idea is there.

