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) 中排序符号

参见 how to reverse a list with O(1) space and O(n) time?