如何以遞歸方式通過鏈接列表引用作爲參數傳遞鏈接列表[作業]

Question

對於此作業，我需要以鏈接列表作爲參數而不是節點以遞歸方式反向打印鏈接列表。

我也有使用，我的教授提供的這個SinglyLinkedList類：

public class SinglyLinkedList<E> { 
    private int length; // # elements in the linked list 
    private SLNode<E> head; // access point to the linked list 
    private SLNode<E> tail; 

    public SinglyLinkedList() { 
    this.length = 0; 
    this.tail = new SLNode<E>(); // the tail dummy node 
    this.head = new SLNode<E> (null, this.tail); // the head dummy node 
    } 

    public int getLength() { 
    return this.length; 
    } 

    public void add(E e) { 
    SLNode<E> newnode = new SLNode<E> (e, null); 
    newnode.setSuccessor(this.head.getSuccessor()); 
    this.head.setSuccessor(newnode); 
    this.length++; 
    } 

    public void add(E e, int p) { 
    // verify that index p is valid 
    if ((p < 0) || (p > this.length)) { 
     throw new IndexOutOfBoundsException("index " + p 
              + " is out of range: 0 to " + 
              this.length); 
    } 
    SLNode<E> newnode = new SLNode<E> (e, null); 
    SLNode<E> cursor = this.head; 
    for (int i = 0; i < p; i++) { 
     cursor = cursor.getSuccessor(); 
    } 
    addAfter(cursor, newnode); 
    this.length++; 
    } 

    public E remove(int p) { 
    if ((p < 0) || (p >= this.length)) { 
     throw new IndexOutOfBoundsException("index " + p 
              + " is out of range: 0 to " + 
              (this.length - 1)); 
    } 
    SLNode<E> cursor = head; // good for p == 0 
    if (p > 0) { 
     cursor = find(p - 1); // get target's predecessor 
    } 

    SLNode<E> target = cursor.getSuccessor(); // get the node to remove 

    // link target to cursor's successor 
    cursor.setSuccessor(target.getSuccessor()); 
    target.setSuccessor(null); 
    cursor.setElement(null); 
    this.length--; 
    return target.getElement(); 
    } 

    public E getElementAt(int p) { 
    SLNode<E> node = this.find(p); 
    return node.getElement(); 
    } 

    private void addAfter(SLNode<E> p, SLNode<E> newnode) { 
    newnode.setSuccessor(p.getSuccessor()); 
    p.setSuccessor(newnode); 
    } 

    private SLNode<E> find(E target) { 
    SLNode<E> cursor = head.getSuccessor(); 

    while (cursor != tail) { 
     if (cursor.getElement().equals(target)) { 
     return cursor; // success 
     } 
     else { 
     cursor = cursor.getSuccessor(); 
     } 
    } 
    return null; // failure 
    } 

    private SLNode<E> find(int p) { 
    if ((p < 0) || (p >= this.length)) { 
     throw new IndexOutOfBoundsException(); 
    } 

    SLNode<E> cursor = head.getSuccessor(); 
    int i = 0; 

    while (i != p) { 
     cursor = cursor.getSuccessor(); 
     i++; 
    } 

    return cursor; 
    } 

} 

我無法弄清楚如何編寫方法與參考傳遞到一個單向鏈表，而不是一個節點。先謝謝您的幫助！

Answer 1

基本情況是列表爲空，沒有任何可打印的內容。所以我們先檢查一下。如果滿足基本情況，我們將返回而不打印任何內容。否則，列表中的元素仍然存在，所以我們從列表中取出最後一個元素（因爲我們正在反向打印）並將其從列表中彈出。 remove方法返回被刪除的元素，所以應該這樣做。現在我們遞歸我們的修改列表（減去最後一個元素）。最終，列表將是空的，並且所有元素都將被反向打印。

public static <E> void printReverse(final SinglyLinkedList<E> list) { 
    if(list.getLength() > 0) { 
     System.out.println(list.remove(list.getLength()-1)); 
     printReverse(list); 
    } 
} 

Answer 2

還沒有研究你的代碼深，而只是印刷應該是很簡單的：

在僞代碼：

printLinkedListInReverse(node) { 
    if (node has no next) { 
     print out node itself 
    } else { 
     printLinkedListInReverse(node's next) 
     print out node itself 
    } 
} 

簡言之，在反向打印，要打印出剩下的列表中排除自身首先，和打印節點本身

---

如果你不能得到內部節點的保持，鏈表進行修改，然後將W ay仍然類似：

printLinkedListInReverse(list) { 
    if (list is empty) { 
     //do nothing 
    } else { 
     firstElement = list.remove(0) 
     printLinkedListInReverse(list) // print the remaining list first 
     print firstElement 
    } 
}