我的代码的 space 复杂度是多少？ （链表）

Question

我正在解决一个与链表相关的问题，我写了一些工作得很好的代码，但我无法分析我的代码的 space 复杂性。这就是问题所在，你已经得到了一个整数的单链表以及两个整数，'M,' 和 'N.' 遍历链表，这样你就可以保留 'M'节点，然后删除下一个 'N' 个节点。以此类推，直到链表结束。

我写了这段代码来解决这个问题。

Node *skipMdeleteN(Node *head, int M, int N) {
  if (head == NULL) return head;
  if (M == 0) return NULL;
  if (N == 0) return head;
  Node *current = head;
  Node *dummy1 = new Node(-1);
  Node *dummy2 = new Node(-1);
  Node *FinalHead;
  Node *dummy2Head;
  Node *prev;
  int i = 0;
  int j = 0;
  int Head = 0;
  while (current != NULL) {
    if (i <= M - 1) {
      dummy1->next = current;
      dummy1 = dummy1->next;
      if (Head == 0) {
        FinalHead = dummy1;
        Head++;
      }
    }
    if (i >= M && i <= ((M + N) - 1)) {
      dummy2->next = current;
      dummy2 = dummy2->next;
      if (j == 0) {
        dummy2Head = dummy2;
        j++;
      }
    }
    if (i == ((M + N) - 1)) {
      i = 0;
    } else {
      i++;
    }
    current = current->next;
  }
  dummy1->next = NULL;
  dummy2->next = NULL;
  dummy1 = dummy1->next;
  dummy2 = dummy2->next;
  while (dummy2Head != NULL) {
    prev = dummy2Head;
    dummy2Head = dummy2Head->next;
    delete (prev);
  }
  return FinalHead;
}

此代码运行良好，代码背后的逻辑如下：

我创建了 2 个虚拟节点（dummy1 和 dummy2），然后我开始遍历链表，对于前 M 个节点，我继续将这些节点附加到 dummy1 节点的末尾。完成 M 个节点后，我开始在 dummy2 节点的末尾附加下一个 N 个节点，我将在最后删除该节点。因此，这会将我想保留的所有 M 节点附加到 dummy1 列表的末尾，其头部 I return.

我的代码的时间复杂度是O(N)，因为我是遍历列表。我不确定 space 复杂度是多少，使用 2 个虚拟节点是否会使它成为线性 space 复杂度，因为它们就像一个链表。请解释！

Answer 1

有两个 space complexity 指标：总 space 复杂度和辅助（额外）space 复杂度。

总计包括输入，辅助不包括。

在你的例子中，输入大小是 O(n)，你正在修改它，使用 O(1) extra space。修改后，输入仍然是 O(n)。这里 n 表示列表的大小。

这转化为 O(n) 总 space 复杂度和 O(1) 辅助 space 复杂度。