c - 使用递归从末尾开始的第 n 个节点(链表)

Question

任何人都可以解释一下这实际上是如何工作的吗？我无法理解递归，递归到达链表末尾后会发生什么，以及如何展开以及操作(增量和 if 条件检查)？

Linked List

void printNthFromLast(struct node* head, int n) 
{
static int i = 0;
if(head == NULL)
   return;
printNthFromLast(head->next, n);
if(++i == n)
   printf("%d", head->data);
}

Answer 1

如果传递给函数的 struct node* 为 NULL，则该函数返回。如果链表有零个节点或者我们已经到达链表的末尾，就会发生这种情况。

if(head == NULL)
    return;

否则，该函数的每个实例都将在此行等待其“子”返回:

printNthFromLast(head->next, n);

在到达列表末尾之前不会进行任何打印。一旦我们到达列表的末尾，调用的最终函数将在 if 语句中返回，因为 head == NULL，因为我们位于末尾。

该函数的每个实例现在将继续执行这些行(一旦它的“子”返回):

if(++i == n)
    printf("%d", head->data);

基本上是从后面开始数。每个实例将 i 加 1，然后检查它是否等于我们提供的数字 n。如果是，则打印数据。否则，它就会结束，并且它的“父级”有机会执行这些行。

编辑:这确实是一种非常糟糕的方式来完成您正在做的事情。如果列表相当大，您的程序可能会耗尽堆栈内存。您应该通过迭代来完成此操作。