0

嗨，我想知道如何去反转一个单链表。从到目前为止我看到的示例中，反向方法的返回类型为 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.js 时如何返回 SLL 类型的列表。我也认为我的退货声明可能是错误的。

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

提前致谢！

4

1 回答 1

1

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 结果，而应返回无效。

希望这可以帮助。

于 2013-05-12T01:02:58.103 回答