递归插入排序列表

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

创建一个函数，该函数需要一个起始节点和要插入的数据。

如果该节点是放置数据的正确位置，请将其插入。

如果没有，则递归调用该函数以尝试下一个节点。