1

假设有一个长度未知的单链表。我们想找到到尾部有 M 步的节点。

例如，单列表是这样的：(A)->(B)->(C)->(X)->(Y) 和 M = 2。那么输出应该是指向 (C) 的指针。

面对这个测验，我的第一反应是遍历单链表得到长度N。然后第二次遍历单链表，但只向前NM-1步。时间复杂度为 O(n)，空间复杂度为 O(1)。

然后，我面临的挑战是找到一种解决方案以单次遍历的方式进行。解决方案是有两个指针。第二个指针比第一个指针落后 M 步。这两个指针以相同的速度向前移动。当第一个指针到达尾部时，第二个指针就是结果。

经过对这个问题的深入思考，我真的不相信第二个“棘手”的解决方案比第一个更好。它是一次遍历，但它也涉及 2*NM 指针分配。

有没有想过这个问题？还有其他真正更快的解决方案吗？

4

5 回答 5

3

您应该使用循环缓冲区

分配一个 M + 1 个指针的数组，并通过列表为每个节点填充第 (i mod M + 1) 个指针。当你到达终点时，在数组中回看 M（如果需要，可以环绕）。

这样，您只有 N 次写入！

这是 C++ 中的 hack 作业示例程序

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 个错误检查为关闭。我的指针语法也可能有点偏差，但想法就在那里。

于 2009-01-20T04:49:20.627 回答
0

除了您提出的计数式算法之外，您可以使用类似于以下的递归函数：

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

当然，当函数返回您要查找的数字时，您需要找到一种存储相关节点的好方法。

（编辑：这可能不会比计数算法更有效，只是一种替代方法）

然而，这个问题的真正答案是：您的数据结构（单链表）不利于快速实现您想要对其执行的操作，因此您应该选择一个新的数据结构。

于 2009-01-20T04:42:56.850 回答
0

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

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

于 2009-01-20T04:46:50.320 回答
0

可以通过 N+4M 指针分配和 log(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[front] 现在是你的答案

于 2009-01-20T08:51:44.037 回答
-1

我认为更好的东西是这样的：

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)。

于 2009-01-20T06:26:23.753 回答