找到第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（）方法負責處理傳遞給它的節點爲空的場景。