java - 这种反向单链表算法的复杂性？

Question

这个算法的复杂度是多少？我假设它是 O(N) 但我想澄清一下。如果我在链表中​​有一个尾巴，我会假设这会更快，因为我会完全避免让 while(current != null) 循环循环到链表的末尾。

public void reverse() {
    Stack<Node> stack = new Stack<Node>();
    if (this.head != null || this.head.next != null) {
        Node current = this.head;
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        Node last = null;
        while (!stack.empty()) {
            if (last==null) {
                this.head = stack.pop();
                last = this.head;
                continue;
            }
            last.next = stack.pop();
            last = last.next;
            if (stack.empty()) {
                last.next = null;
            }
        }
    }
}

Answer 1

您通过迭代列表将所有链接列表元素推入堆栈这是一个 N 然后您迭代堆栈是另一个 N 所以您在 O(2N) 中排序符号

看看如何用 O(1) 空间和 O(n) 时间反转列表？

Answer 2

该算法属于 O(N) 类。您正在使用 N 次静态操作量（第一个循环），然后再次使用静态操作量（第二个循环）；Stack.pop() 应该独立于“N”；所以这意味着它在 O(2N+c) 类中......而 O(2N+c) 在 O(2N) 类中，而 O(2N) 类在 O(N) 中。换句话说：例程的运行时间随着堆栈中元素的数量线性增加。

或者简单地说：是的，它属于 O(N) 类。