查找链表的第 k 到最后一个元素

Question

我试图递归地实现它，但我不确定为什么这段代码不起作用（假设我有一个 returns 正确的长度函数）：

Node findk(Node head, int k) {
    if (node_length(head)==k) {
        return head; }
    else {
        return findk(head.next, k-1);}}

谢谢！

Answer 1

您的代码有两个问题：

这是一种可能的解决方法：

Node findk(Node head, int k) {
    if (head == null) return null;
    if (node_length(head)==k) return head;
    return findk(head.next, k);
}

请注意，此解决方案是 O(n²)，因为 node_length 必须是 O(1)，每个 N-k 列表的节点。有几种方法可以更快地完成它 - 例如，通过找到 int m = node_length(head)，然后返回列表开头的第 (m-k) 个节点。

Answer 2

如果你想从末尾找到第K个元素你在递减K的值是错误的，正确的代码如下：

Node findk(Node head, int k) {
  if (node_length(head)==k) {
    return head; 
  } else {
    return findk(head.next, k);
  }
}

另外，我希望您的 node_length() 方法能够处理传递给它的节点为空的情况。

Finding the kth to the last element of a linked list