复制SkipList /链接列表

Question

在编程分配中，我需要克隆一个链接列表(它是一个复制构造函数，所以除了克隆之外不返回任何内容)。旧的链接列表将经历一些删除和添加元素，但是新克隆的链接列表应该保持不变。我该怎么做？当我移除并向旧列表中添加新节点时，它也会对新链接列表执行相同的操作。我怎么才能避免这种情况？

  this->head = other.head;
  this->head->val = other.head->val;

  SNode *curr = other.head->next;
  SNode *newCurr = nullptr;
  while (curr != nullptr) {
    newCurr = curr;
    curr = curr->next;
  }
}

我尝试过上面的代码，但是当我修改旧列表，即添加和删除节点时，它也会从新列表中添加和删除节点。我能做些什么来避免新列表上发生的修改？

Answer 1

您的代码没有创建新节点，因此无法工作。克隆的列表应该由新节点组成，因此应该调用SNode构造函数。

例如：

this->head = other.head;

这将使新列表指向同一个列表:现在有两个head指针指向同一个头节点。因此，下面的赋值并没有做任何有用的事情，因为它实际上是将一个成员的自身价值分配给自己：

this->head->val = other.head->val;

循环也没有做任何有用的事情，因为它没有将任何东西分配给属于新结构的任何成员。它只分配给变量，使用两个变量遍历原始列表，其中newCurr落后于curr一步。

下面是对您的片段的更正：

  // Deal with boundary case: empty list
  this->head = NULL;
  if (other.head == NULL) return; // Nothing more to do.
  
  // Clone the head node
  this->head = new SNode(other.head->val);

  SNode *curr = other.head->next;
  SNode *tail = this->head; // tail is a more descriptive name
  while (curr != nullptr) {
    tail->next = new SNode(curr->val); // Clone current node and append it
    tail = tail->next; // This new node is now the tail
    curr = curr->next;
  }

这假设您有一个SNode构造函数，该构造函数为节点的值接受一个参数。