java - 如何反向单链表-Java

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center作为指导。




7年前关闭。





嗨，我想知道如何反转单个链接列表。从到目前为止我看到的示例中，反向方法的返回类型为void，而我需要一个具有单链接列表（SLL）返回类型的方法。我有一个称为Node的内部类来处理所有节点引用。

这是我到目前为止的内容：

public SLL<E> reverse() {
    Node<E> first = null;
    Node<E> current = this;  // produces compilation error
    while (current != null) {
        Node<E> save = current;
        current = current.next;
        save.next = first;
        first = save;
    }
    return first;
}

我收到以下编译错误：

错误：不兼容的类型
必需：myprog.SLL.Node
找到：myprog.SLL

我只是想知道在处理Node时如何返回SLL类型的列表。我也认为我的退货声明可能是错误的。

如果您需要更多代码来理解我的问题，请问:)

提前致谢！

最佳答案

SLL应该是一个类，其“ head”或“ first”指针指向列表中的第一个节点。

如果您打算返回SLL，则大概是带有新节点的新SLL，并以与原始节点相反的顺序复制。

public SLL<E> reverse() {
    SLL<E> result = new SLL<E>();

    // copy Nodes into new list, in reverse order.
    //
    Node<E> read = this.first;
    while (read != null) {
        // insert Copy, first;
        Node<E> copy = new Node<E>( read.getItem());
        copy.next = result.first;
        result.first = copy;
        // advance 'Read Position'.
        read = read.next;
    }

    // done.
    return result;
}

如果您将原始SLL更改为就地反转（尚未检查您的代码是否还适用于此功能），则不应返回SLL结果，而只是返回无效结果。

希望这可以帮助。