java - 查找单向链表的倒数第 K 个元素

Question

我目前正在阅读《Crack the Coding Interview》(第 5 版)一书。其中有一个特殊的问题，它说实现一个算法来查找单向链表的第 k 个元素。针对该问题讨论了多种方法。我对递归解决方案特别困惑。它是这样的(无耻地从书中复制它):

public class IntWrapper {
    public int value = 0;
}

LinkedListNode nthToLastR2(LinkedListNode head, int k, IntWrapper i){
    if(head == null){
        return null;
    }
    LinkedListNode node = nthToLastR2(head.next, k, i);
    i.value = i.value + 1;
    if(i.value == k) {      // We've found the kth element
        return head;
    }
    return node;
}

我的问题是:当我们找到特定节点时，我们将返回一个 LinkedListNode，即使我们没有LinkedListNode > 找到那个特定的节点。所以没有办法从任何其他节点告诉第 k 个节点。谁能告诉我我的观察是否正确？如果是，我们如何才能使其正确(当然除了在 return head 之前执行 System.out.println 因为那只是 print 节点而不是返回它) ?

Answer 1

这个递归函数的诀窍是递归调用先发生——这意味着调用之后的任何代码执行时，我们已经在最后一个节点。一旦我们到达终点，我们的函数将返回 null，因为什么都没有了(head 现在是 null)。我们的调用堆栈的最终函数返回 null，这意味着 node = null。现在函数检查当前节点是否是第 k 个节点(使用累加器 i)。

有两种可能的情况:

1. 我们不在正确的节点:我们的函数只返回 node，我们记得它是 null。因此，对于调用堆栈中的下一个更高的函数，事情看起来就像它已经结束了，除了 i 更大。

2. 我们在正确的节点:我们返回head，而不是node(记住node = null)。在这种情况下，我们再次向上传播调用堆栈，但这次不是 node 在每一层都是 null，而是 head，它是我们想要的节点。最终我们回到顶部，并返回正确的元素。

所以，简单地说，该函数一直返回 null，直到我们找到该元素，然后它一直返回该元素。

画得不好的mspaint图片: