为什么我的教科书说空间复杂度是O（1）？

Question

为什么我的教科书说此算法的空间复杂度是O（1）？我觉得它所持有的链表的大小为O（n）。

 public static LinkedListNode nthToLast(LinkedListNode head, int k) {
    LinkedListNode p1 = head;
    LinkedListNode p2 = head;

    /* Move p1 k nodes into the list.*/
    for (int i = 0; i < k; i++) {
        if (p1 == null) return null; // Out of bounds
        p1 = p1.next;
    }

    /* Move them at the same pace. When p1 hits the end, 
     * p2 will be at the right element. */
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

Answer 1

该算法执行O（n）次迭代，但是它不会为列表中的元素分配任何内存，它仅使用已经存在的项。使用的唯一内存是局部变量p1和p2，用于指定项目。

Answer 2

空间复杂度是算法使用多少内存作为输入大小的函数。换句话说：如果输入的大小改变了，该算法将使用多少内存？

链表输入是否具有1节点，10节点或1000000节点，该算法使用相同的内存量。它使用一个常量，因为它只分配3个变量（一个常量）-int i，LinkedListNode p1和LinkedListNode p2。

Answer 3

考虑算法的空间复杂性时，应考虑算法显式分配的额外空间。在上面的示例中，在列表中找到第n个到最后一个链接列表节点的算法仅创建了两个附加的LinkedListNode指针p1和p2以及一个计数器i来迭代for循环。该算法的额外内存量与传入的链表的长度无关。无论传递给LinkedListNode的链表是10个节点长还是10个节点长，您仍然会有两个nthToLast()指针和一个整数计数器。长一千万个节点。