遞歸插入排序列表

Question

我需要編寫一個方法，以遞歸方式將項目插入到單個鏈接的排序列表中。該列表中的節點類看起來是這樣的：

protected class Node<T> { 

    protected Node(T data) { 
     this.data = data; 
    } 

    protected T data; 
    protected Node<T> next; 
} 

protected Node<E> head; 

}

的方法簽名是：無效插入（E數據）。 我可以迭代地做到這一點，但我似乎無法圍繞如何遞歸地做我的頭。誰能提供任何見解？

Answer 1

假設你應該插入列表的末尾，只需在this.next上重複，直到this.next爲null。

public void insert(E data) { 
    if (this.next == null) { 
     // we're at the end, so actually do the insert 
     // if you can do it iteratively, you should already know what to do here 
    } else { 
     this.next.insert(data); 
    } 
} 

Answer 2

創建一個函數，該函數需要一個起始節點和要插入的數據。

如果該節點是放置數據的正確位置，請將其插入。

如果沒有，則遞歸調用該函數以嘗試下一個節點。