c++ - 如何使用递归返回单链表中的倒数第 n 个元素？

Question

所以我有这个递归解决方案来打印列表末尾的第 n 个元素:

void print_nth_from_last_rec(Node* node, int n) {

    static int count { 0 };

    if (!node) return;

    print_nth_from_last_rec(node->next, n);

    if (++count == n)
        cout << node->data;

}

但我不知道如何使用递归返回该元素。可能吗？

尝试:

• 如果我有一个静态的 Node* 将被分配到 (++count == n) 时，我可以做到这一点:

  Node* get_nth_from_last_rec(Node* node, int n) {
  
      static int count { 0 };
      static Node* ret{ nullptr };
  
      if (node) {
  
          get_nth_from_last_rec(node->next, n);
  
          if (++count == n)
              ret = node;
      }
  
      return ret;
  }
  

• 也可以传入对 out 节点的引用并将第 n 个元素分配给它。

但是有没有更好的办法呢？这些静力学对我来说看起来不太干净。

Answer 1

Node* get_nth_from_last_rec(Node* node, int& n)
{
    if (node)
    {
        Node* result = get_nth_from_last_rec(node->next, n);
        if (result)
            return result;
        else if (! n--)
            return node;
    }
    return nullptr;
}