我见过的用于迭代合并两个排序链表的大多数实现如下。
我不明白为什么这个过程的空间复杂度是 O(1) 而不是 O(N)？当我们将虚拟节点指向两个链表中的现有节点时，我们实际上是在创建一个新的链表——一个将两个现有链表交织在一起的链表。因此，这是否仍然需要 O(N) 空间？虚拟节点是它自己的链表的头部，它与原来的两个链表是分开的，即使它使用相同的节点......
最佳答案
您完全正确，您将需要 Θ(n) 存储空间来保存合并两个总长度为 n 的列表的结果。但是在函数开始运行之前，有多少存储空间已经存在，又有多少存储空间是新的？你已经有两个总共 n 个元素的列表，所以在你开始这个算法之前你已经使用了 Θ(n) 空间，当你完成后你有相同的列表，只是重新连接以便下一个指针可能指向到不同的地方。因此，您需要为此过程分配的内存量不是 Θ(n)，而是 Θ(1)。
更一般地说，在测量空间复杂度时忽略问题输入所使用的空间是很常见的，因为从某种意义上说，空间成本是不可避免的，而且您无法采取任何措施来消除它。
一条建议是:如果你写出 O(1) 或 O(n) 之类的东西，那么弄清楚你是在测量时间还是空间通常是个好主意。例如，更清楚地说该过程需要 O(n) 内存或 O(1) 时间，而不是说该过程"is"O(n) 或"is"O(1)，因为不清楚你是什么当您这样做时，正在使用大 O 符号进行测量。
关于data-structures - 合并两个已排序的链表——理解为什么它是 O(1) 与 O(N) 空间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42591684/