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

Question

我试图实现这个递归，但我不知道为什么这段代码不起作用（这是假设我有一个长度函数返回正确）：

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

谢谢！

Answer 1

有两个问题与您的代码：

• 你不应该递减k因为你走的列表，并
• 你要注意打null达到k个当元素之前名单太短。

这里是一个可能的修正：

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)-第n个节点。

Answer 2

如果你想找到你到底是递减ķ这是错误的值所述K元素，正确的代码如下：

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

而且我希望你node_length（）方法负责处理传递给它的节点为空的场景。