c - 使用递归从列表中的最后一个元素查找第 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.
  }

1. 我试图看看是否可以使用尾调用递归来解决这个问题， 并且没有静态变量/全局变量。

2. 我正在尝试学习 Haskell 想知道如何以纯函数的方式实现它，而不使用 Haskell 的 length 和 !! 类似 x !! ((长度x)-K)。

所以首先要问，我们如何在 C 中使用递归和无静态/全局变量来做到这一点，只是为了了解一些想法。

任何建议/指示将不胜感激。

谢谢。

Answer 1

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

因此，两指解决方案基于这样的观察:如果我们有两个指针进入列表(两个手指)，并且它们总是相距 n 个元素，因为我们总是将它们推进tandem，那么当前导手指到达列表末尾时，尾随手指将指向我们想要的元素。这是一个简单的尾递归:

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 是正确的。)