linked-list - 使用恒定数量的附加空间反转链表

Question

以下是我反转链表的代码：

public LinkedList reverse() {
    LinkedList m = new LinkedList();
    Node temp = this.getHeadNode();
    while(temp!= null) {
        m.insertFirst(temp.getElement());
        temp = temp.getNext();
    }
    m.getTailNode().setNext(null);
    return m;
}

对于在我的函数中声明的局部变量 LinkedList mi，这是否意味着我正在使用 O(n) 数量的额外空间，或者它被认为是恒定数量的空间？

Answer 1

嗨，我认为一种更好的方法可能是在不创建辅助列表的情况下反转链接列表。

Answer 2

只需三个指针在开始时初始化所有三个假设这些指针是 x,y,z 然后移动 y=x->next,z=y->next ,y->next=x,x=y; 这样做直到 x 到达列表的末尾。

Answer 3

因为您正在创建链表的新实例 - 您将在内存中有 2 个列表副本。该列表将包含对对象的引用，因此如果您想计算对象的实例 - 那么您是安全的并且额外的内存量是 O(1)。但是列表本身需要一些内存，因此如果您计算列表中“单元格”的数量 - 那么是的，您使用了 O(N) 额外的内存。

Answer 4

这就是我所做的：

public LinkedList reverse1() {
    Node temp1 = tail;
    Node temp2 = head;
    Node temp3 = new Node(this.removeFirst());
    temp1.setNext(temp3);
    temp3.setNext(null);
    //head = temp1;
    tail = temp3;
    while(head != temp1) {
        temp2 = new Node(this.removeFirst());
        temp2.setNext(temp3);
        temp1.setNext(temp2);
        temp3 = temp2;
    }
    return this;
}

这够好吗？

Answer 5

这是我在 C# 中实现的线性时间和恒定空间中反转 LinkedList 的方法。我希望它有所帮助。我们只是颠倒节点之间的链接，使第一个节点在最后，最后一个节点在前。

        Node p1, p2, t1, t2;
        p1 = head;
        p2 = p1.next;
        while (p2 != null)
        {
            t1 = p2;
            t2 = p2.next;
            p2.next = p1;
            p1 = t1;
            p2 = t2;
        }
        head.next = null;
        head = p1;