使用指针的链表的空间复杂性

Question

我已经声明了一个类Node，用于在链表中创建新节点，如下所示：

class Node{
constructor(data){
this.data = data;
this.next = null;
}
}

然后我尝试迭代给定的head链表，并希望创建一个新的链表，如下所示：

// head: 1 -> 2 -> 3 -> 4 -> 5 -> x
function doSomething(head){
let linked_list = new Node(head.data);
let linked_list_ptr = linked_list;
let head_ptr = head.next;

while(head_ptr !== null){
linked_list_ptr.next = new Node(head_ptr.data);
linked_list_ptr = linked_list_ptr.next;
head_ptr = head_ptr.next;
}

return linked_list;
}

我的问题是，这个函数或代码的空间复杂性是多少？因为一开始我创建一个节点，然后使用pointer创建新节点并遍历链表。我认为时间复杂性将是O(n)，但空间复杂性呢？

Answer 1

我认为时间复杂度将是O(n)。。。

没错。

。。。但空间的复杂性又如何呢？

它也是O()，因为您的代码使用new运算符构造Node实例的时间。第一个在循环外创建，另一个−1在循环内创建。

其他变量，如head_ptr、linked_list_ptr、linked_list和head，都是需要O(1)空间的对象引用，因此总的空间复杂度为O()。

旁注：函数假定列表不为空。您需要涵盖head是null的情况。