对以下算法的 space 复杂性感到困惑
Confused with space complexity of following algorithm
我在看问题 Link and it tells that space complexity of solution is O(1) (read answer by Max)。我怀疑 space 复杂度是算法所需的 space 并且我理解正确并且感觉它肯定是 O(n) 其中 n 是链表的大小。谁能告诉我是答案错了还是我理解有误？
Max link、here 中的答案摘要显然是错误的。
O(1) space 复杂性根据定义是不可能的，如果目标是复制一些可变数量的数据（在这种情况下 linked 列表）。
这在算法的描述中可以看到：
Create the copy of node 1 and insert it between node 1 & node 2 in
original Linked List, create the copy of 2 and insert it between 2 &
3.. Continue in this fashion, add the copy of N afte the Nth node
Blockquote
在这里，回答者刚刚添加了 "N" 个节点，所以它至少是 O(n) 复杂度（而且，实际上， space 所列算法的复杂度 是 O(n)).
我在看问题 Link and it tells that space complexity of solution is O(1) (read answer by Max)。我怀疑 space 复杂度是算法所需的 space 并且我理解正确并且感觉它肯定是 O(n) 其中 n 是链表的大小。谁能告诉我是答案错了还是我理解有误？
Max link、here 中的答案摘要显然是错误的。 O(1) space 复杂性根据定义是不可能的，如果目标是复制一些可变数量的数据（在这种情况下 linked 列表）。
这在算法的描述中可以看到：
Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node Blockquote
在这里，回答者刚刚添加了 "N" 个节点，所以它至少是 O(n) 复杂度（而且，实际上， space 所列算法的复杂度 是 O(n)).