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

Question

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?

Answer 1

Other than your proposed counting-style algorithm, you could use a recursive function similar to:

int getNumNodesAfter(Node *node){
   if( node->next == NULL ){
      return 0;
   }else{
      return getNumNodesAfter(node->next) + 1;
   }
}

Of course, you'll want to find a good way to store the node in question when the function returns the number you're looking for.

(Edit: this is not likely more efficient than the counting algorithm, just an alternative)

The real answer to the question, though, is: your data structure (singly linked list) does not facilitate a fast implementation of the operation you want to perform on it, so you should choose a new data structure.

Answer 2

I like the recursive suggestion. However, I don't believe it will increase performance over the double pointer algorithm in the question.

Rubancache is correct in that the data structure doesn't support faster operations. It is made for slow traversals but with fast insertion times.

Answer 3

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.

Answer 4

I think something a little better would be something like:

FindNFromEnd(head, n)
    counter = 0;
    first = head
    firstplusn = head
    while (head.next != null)
        counter++
        head = head.next

        if counter == n
            first = firstplusn
            firstplusn = head
            counter = 0

     while counter < n
         counter++
         first = first.next

     return first

for example, if n = 3, it would look something like:

    0   1   2   3   4   5   6   7
1   FNH
2   FN  H   
3   FN      H
1   F           NH 
2   F           N   H
3   F           N       H
1   F           N           H
2               F           N   H
---
3                  [F]

So F keeps track of head - N - counter, N keeps track of head-counter, and you only need to do something (N + M + N/M) rather than O(2*N - M).

Answer 5

Can be done with N+4M pointer assignments and log(M) space (well, extra space, your list already takes up N). Here's how (the idea is the same idea people use in go-back debuggers). Pseudo code follows, where M < 2^m, and p is a circular buffer of length m

for (n=0, front = 0; p[front] != end; ++n, ++p[front]) {
  for (j = 0; j < m; ++j)
    if (n % j = 0)
      ++ front
  front = front % m
}
front = (front-1) % m
for (j = M; j < n-2^m - (n mod 2^m); ++j)
  ++p[front]

p[front] is now your answer