合并两个有序链表的GFG题解空间复杂度为何是O(1)

空间复杂度为O(1)的原因解释 #

• 我们计算算法空间复杂度时，仅统计除输入、输出之外额外申请的辅助空间，输入本身的存储空间、输出结果复用的输入空间都不会被计入统计。
• 这段代码全程只额外申请了1个dummy哨兵节点，以及1个用来遍历拼接的tail指针，这两个变量的占用空间是固定常数，不会随着两个链表的长度M、N的增长而变化。
• 你误解的核心点在于：代码没有新建任何存储实际数据的节点，所有节点都是直接复用两个输入链表的原有节点，只是修改了原有节点的next指针指向，把两个链表的节点重新按顺序拼接，完全没有申请和M、N规模相关的线性空间。
• 这里的哨兵节点仅用来简化边界处理（避免单独判断合并后链表的头节点属于哪个输入链表），属于常数级别的额外开销，因此整体空间复杂度为O(1)。

内容的提问来源于stack exchange，提问作者Mudit Kumar