使用递归查找列表中最后一个元素的第 n 个元素

Question

我们可以在 C 语言中使用静态变量解决这个问题，如下面的代码片段 (like the function found in this page)。

static int i = 0;
if(head == NULL)
   return;
getNthFromLast(head->next, n);
if(++i == n)
  {THIS IS THE NTH ELEM FROM LAST
   DO STUFF WITH IT.
  }

我想看看我是否可以使用尾调用递归来解决这个问题，并且没有静态 variables/global 变量。
我正在尝试学习 Haskell 想知道如何以纯功能方式实现它，而不使用 Haskell的length和 !! 类似于 x !! ((length x) - K).

所以开始问，我们如何在 C 中使用递归和没有 static/global 变量来做到这一点，只是为了获得一些想法。

任何 suggestions/pointers 将不胜感激。

谢谢。

Answer 1

典型的迭代策略使用两个指针并在开始移动另一个之前将一个指针运行到 n - 1。通过递归，我们可以通过添加第三个参数来使用堆栈从列表末尾开始倒计时。为了保持用法简洁，我们可以创建一个静态辅助函数（在这个意义上它意味着只在编译单元内可见，与具有函数作用域的静态变量完全不同的概念）。

static node *nth_last_helper(node* curr, unsigned int n, unsigned int *f) {
  node *t;
  if (!curr) {
    *f = 1;
    return NULL;
  }
  t = nth_last_helper(curr->next, n, f);
  if (n == (*f)++) return curr;
  return t;
}

node* nth_last(node* curr, unsigned int n) {
  unsigned int finder = 0;
  return nth_last_helper(curr, n, &finder);
}

或者我们实际上可以在没有额外参数的情况下进行计数，但我认为这不太清楚。

static node *nth_last_helper(node* curr, unsigned int *n) {
  node *t;
  if (!curr) return NULL;
  t = nth_last_helper(curr->next, n);
  if (t) return t;
  if (1 == (*n)--) return curr;
  return NULL;
}

node* nth_last(node* curr, unsigned int n) {
  return nth_last_helper(curr, &n);
}

请注意，我使用无符号整数来避免为列表中的 "negative nth last" 值选择语义。

然而，这些都不是尾递归的。为此，您可以更直接地将迭代解决方案转换为递归解决方案，如 .

Answer 2

链接页面解释了如何用双指解决问题；他们不简单地编写递归版本，这会简单明了，这有点令人惊讶。（根据我的经验，当有一个简单明了的版本同样有效时，你不会通过提供棘手和晦涩的代码在面试中取得成功。但我想有些面试官会看重晦涩的代码。）

因此，双指解决方案基于以下观察：如果我们有两个指向列表的指针（两个手指），并且它们总是相隔 n 个元素，因为我们总是将它们串联推进，然后当前导手指到达列表末尾时，尾随手指将指向我们想要的元素。这是一个简单的尾递归：

Node* tandem_advance(Node* leading, Node* trailing) {
  return leading ? tandem_advance(leading->next, trailing->next)
                 : trailing;
}

对于初始情况，我们需要前导指针是从列表开头开始的 N 个元素。另一个简单的尾递归：

Node* advance_n(Node* head, int n) {
  return n ? advance_n(head->next, n - 1)
           : head;
}

那么我们只需要将两者放在一起即可：

Node* nth_from_end(Node* head, int n) {
  return tandem_advance(advance_n(head, n + 1), head);
}

（我们最初前进 n+1 以便从末尾开始的第 0 个节点将是最后一个节点。我没有检查所需的语义；可能 n 是正确的相反。）

Answer 3

在Haskell中，双指解决方案似乎是显而易见的方法。如果请求的元素不存在，此版本将以各种方式出错。我将把它作为练习留给你来解决这个问题（提示：编写 drop 和 last 的 return Maybe 值的版本，然后将计算与>>=)。请注意，这会将列表的最后一个元素设为从末尾算起的第 0 个。

nthFromLast :: Int -> [a] -> a
nthFromLast n xs = last $ zipWith const xs (drop n xs)

如果您想手动执行一些递归，No_signal 表示性能更好，

-- The a and b types are different to make it clear
-- which list we get the value from.
lzc :: [a] -> [b] -> a
lzc [] _ = error "Empty list"
lzc (x : _xs) [] = x
lzc (_x : xs) (_y : ys) = lzc xs ys

nthFromLast n xs = lzc xs (drop n xs)

我们不用手动写出 drop，因为库中相当简单的版本几乎是最好的。与此答案中的第一个解决方案或 "reverse, then index" 方法不同，使用 lzc 的实现只需要分配恒定数量的内存。

Answer 4

我假设你的代码丢失了

getNthFromLast(list *node_ptr, int n) {

就在顶部。 (!!)

您的递归版本在其调用堆栈帧中跟踪 node_ptrs，因此它本质上 是非尾递归的。此外，它继续展开堆栈（返回调用帧的堆栈），同时递增 i 并仍然检查其是否等于 n，甚至 after 它已经找到了它的目标 n 个节点；所以没有效率。

那将是一个迭代版本，确实可编码为尾递归，它在前进的路上做事，因此可以在达到目标后立即停止。为此，我们从一开始就打开 n 长度差距，而不是在到达终点之后。我们没有像您的递归版本那样倒数，而是正数。这与此处已经提到的两点法相同。

在伪代码中，

end = head; 
repeat n: (end = end->next); 
return tailrec(head,end)->payload;

其中

tailrec(p,q) { 
    if(NULL==q): return p; 
    else: tailrec(p->next, q->next);
}

这是从 1 开始的，假设 n <= length(head)。 Haskell 代码已在另一个答案中给出。

这种技术被称为 tail recursion modulo cons，或者在这里，modulo payload-access.

Answer 5

nthFromLast lst n = reverse lst !! n

因为Haskell是懒惰的，这应该足够有效

如果你不想使用!!，你必须自己重新定义它，但这很愚蠢。

使用递归查找列表中最后一个元素的第 n 个元素

find nth element from the last in a list using recursion

c

haskell

recursion

tail-recursion