如何以递归方式通过链接列表引用作为参数传递链接列表[作业]

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