2015-01-09 101 views
1

我試圖實現這個遞歸,但我不知道爲什麼這段代碼不起作用(這是假設我有一個長度函數返回正確):找到第k個鏈接列表的最後一個元素

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

謝謝!

+0

你需要返回什麼?第K個元素的位置? – Kakarot 2015-01-09 19:41:13

+0

你正在旋轉成無限遞歸嗎?當head.next爲空時會發生什麼?是否有堆棧跟蹤? – 2015-01-09 19:43:01

+0

你的意思是不工作?你想從頭到尾找到第K個元素嗎? – Kakarot 2015-01-09 19:43:11

回答

0

有兩個問題與您的代碼:

  • 你不應該遞減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個節點。

+0

堆棧上是否有可能發生的問題?我正在閱讀Cracking the Coding interview,作者說我們不能「回傳節點通過堆棧」遞歸回答這個問題 – honeysingh 2015-01-09 20:01:51

+0

@honeysingh當列表太多時,這裏最大的與堆棧相關的問題會溢出堆棧長。但是,如果編譯器執行尾部調用優化,則不會有問題。 – dasblinkenlight 2015-01-09 20:04:54

0

如果你想找到你到底是遞減ķ這是錯誤的值所述K元素,正確的代碼如下:

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

而且我希望你node_length()方法負責處理傳遞給它的節點爲空的場景。