查找指向节点指针的算法

你应该使用循环缓冲区

分配一个m+1指针数组,并通过列表为每个节点填写第(imodm+1)个指针。当你到达终点时,回过头来看看数组中的m(如果需要的话,可以绕一圈)。

这样,你就只有N个字了!

这里是一个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;
}

这应该由1个错误检查为关闭。 我的指针语法可能也有点偏离,但想法是有的。

我喜欢递归的建议。但是,我不相信它会比问题中的双指针算法提高性能。

rubancache是正确的,因为数据结构不支持更快的操作。它是为慢速遍历而设计的,但插入时间很快。

除了建议的计数式算法外,还可以使用类似于以下内容的递归函数:

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

当然,当函数返回您要查找的编号时,您会希望找到一种存储有问题的节点的好方法。

(编辑:这可能不比计数算法更有效,只是另一种选择)

不过,这个问题的真正答案是:您的数据结构(单链表)不便于快速实现要对其执行的操作,因此您应该选择一个新的数据结构。

可以使用n+4M指针分配和日志(m)空间(好吧,额外的空间,您的列表已经占用n)。下面是如何实现的(这个想法和人们在返回调试器中使用的想法是一样的)。下面是伪代码,其中m<2^m,p是长度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[前面]现在是你的答案

我觉得更好的是:

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

例如,如果n=3,它看起来像:

    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]

所以f跟踪head-n-counter,n跟踪head-counter,你只需要做一些事情(n+m+n/m),而不是o(2*n-m)。