在雙向鏈表的末尾遞歸插入

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 
    } 
}