在双向链表的末尾递归插入

Question

我有一个双向链表，我想递归地在链表的末尾插入一个元素。我现在有一种方法可以在不递归的情况下执行此操作，并且可以正常工作。我似乎无法理解如何使用递归来做到这一点。我认为使用递归在单链表的末尾插入是很容易理解的，所以我希望有人能解释一下当链表是双向链表时如何做到这一点。这是我想要递归的正常插入方法：

public void insert(T element) {
    Node in = new Node(element);

    if (in == null) {
        first = in;
    } else {
        Node tmp = first;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = in;
        in.prec = tmp;
    }
}

Answer 1

想法只是用函数调用重写 while 循环：

public void insert(T element) {
    insert(element, first);    // initialization
}

private void insert(T e, Node n) {
    if(n == null) {            // if the list is empty
        first = new Node(e);
    } else if(n.next == null) {       // same condition as in the while loop
        None newNode = new Node(e);
        n.next = newNode;
        newNode.prec = n;
    } else {
        insert(e, n.next);    // looping
    }
}

在双向链表的末尾递归插入

Recursively insert at the end of doubly linked list

java

recursion

insert

linked-list

doubly-linked-list