-2

我有两个班，ListNode和MyList。

列表节点：

public class ListNode {
    private String str;
    private ListNode next;
    public ListNode(String str) {
        this.str = str;
        next = null;
    }
    public String getString() {
        return str;
    }
    public ListNode getNext() {
        return next;
    }
    public void setNext(ListNode next) {
        this.next = next;
    }
}

我的列表

public MyList RecReverse() { //my attempt at the recursive method
    if (head.getNext() == null) {
        return this;
    }
    MyList remainder = new MyList();
    remainder.head = head.getNext(); //start rest of list at the 2nd thing
    ListNode temp = new ListNode(head.getString()); //get the first thing in list
    temp.setNext(null); //set to null to indicate end of list

    remainder.RecReverse(); //reverse the remaining things in the list
    remainder.head.setNext(temp); //then add it to the end of the reversed list

    return remainder;



}

所以你可以看到这个MyList类有一个ListNode我们需要使用的变量。要求该RecReverse方法不带参数并返回一个MyList对象。该方法还必须使用函数Rev(L) = Rev(L`).x，其中L`是列表的其余部分，并且x是列表中的第一件事。

目前，当我反转列表并打印它时，它只打印以下内容：

二

一

在控制台中

4

2 回答 2

2 
public MyList RecReverse() { //my attempt at the recursive method
    if (head.getNext() == null) {
        return this;
    }

    MyList remainder = new MyList();
    remainder.head = head.getNext(); // New list has rest of this list (after head)
    ListNode temp = new ListNode(head.getString()); // save the first thing in list

    remainder = remainder.RecReverse(); //reverse the things in the new 2nd part list

    remainder.end().setNext(temp); // put old head on the end

    return remainder;

}

private ListNode end() {
    ListNode curr = head;
    while (curr.getNext() != null) {
        curr = curr.getNext();
    }
    return curr;
}
于 2013-01-30T00:04:18.323 回答
1

如果您设法保留原始列表的尾部，您将得到正确的结果。问题在于，在每个递归调用中，您都组装了正确的列表，但返回了包含 2 个元素的列表。有关正确解决方案，请参阅 Lee Meador 的答案；如果将末尾保留在列表结构中，则可以对其进行优化。

于 2013-01-30T00:10:08.493 回答