当这种方法点击-时，我正在解决这个问题
给定一个链表和一个整数x。您的任务是完成函数deleteAllOccurces()，该函数删除链表中出现的所有键x。该函数接受两个参数：链表的头和一个整数x。该函数应返回修改后的链表的头。
我不确定我的代码的空间复杂性是多少。
我认为，由于我只使用了1个额外的节点空间，同时创建新节点和删除旧节点，所以它应该是O(1)。
Node* deleteAllOccurances(Node *head,int x)
{
Node *new_head = new Node(-1);
Node *tail = new_head;
Node *temp = head;
Node *q;
while(temp != NULL) {
if(temp->data != x) {
tail->next = new Node(temp->data);
tail = tail->next;
}
q = temp;
delete q;
temp = temp->next;
}
tail->next = NULL;
return new_head->next;
}
嗯，有点。
这取决于你是否将总分配视为净变化(在这种情况下你是对的)。
但是如果您考虑的是新分配的堆次数，那么它将使用更多的空间和大量的计算。(给定的C++编译器和运行时没有义务保证立即重用堆中释放的空间，只是可供重用。)
作为一名几十年的C++程序员，你所做的事情有点可怕，因为你正在进行大量的新分配。这将导致对堆分配结构的猛烈抨击。
此外，你这样做的方式是把不匹配的东西推到列表的末尾，这样你就可以把内容拖下来。
提示-您不需要创建任何新节点。
是的，由于您在任何一次分配的空间大小不取决于参数(例如列表的长度或列表中有多少x值)，因此函数的空间复杂度为O(1)
空间复杂性的实际意义在于查看您的算法需要多少内存。您永远不需要超过1个节点的内存(加上局部变量)，O(1)反映了这一点。
衡量复杂性在一定程度上取决于您认为的变量。就列表中的节点数量而言，您的算法在空间使用方面为O(1)。然而，在这种情况下，这可能不是最好的视角。
这种情况下的另一个变量是节点的大小。复杂性分析经常忽略这一方面，但我认为在这种情况下它是有价值的。虽然算法的空间需求不取决于节点的数量，但它确实取决于节点大小。节点中的数据越多，所需的空间就越大。设s为单个节点的大小；可以公平地说，您的算法的大小要求是CCD_ 6。
即使考虑到节点的数量和每个节点的大小，该任务的更常见算法的大小要求也是O(1)。(它不需要创建任何节点，也不需要复制数据。)我不推荐你的算法。
为了避免全部负面，我认为您的方法是对传统方法的两个独立更改。一个变化是引入了伪节点CCD_ 8。即使您的实现会泄漏内存，这种更改也是有用的(事实上正在使用中)。它的效率仅略低于不使用伪头，并且简化了从列表前面删除节点的逻辑。只要节点大小不太大，这就很好。
另一个变化是切换到复制节点，而不是移动节点。这是一个值得尴尬的改变，因为它免费地为程序员、编译器和执行添加了工作。渐近分析(big-O)可能不会注意到这个加法，但它没有任何有益的收益。你破坏了链接列表的一个关键好处，却一无所获。
让我们考虑放弃第二个更改。您需要添加一行，特别是将new_head->next初始化为head，但这可以通过消除最后将tail->next设置为nullptr的需要来平衡。另一个添加是else子句，因此当前每次迭代运行的行不一定每次迭代都运行。除此之外，还有代码删除和一些名称更改：删除temp指针(改为使用tail->next)，并放弃在循环中创建新节点。总之，与代码相比，这些更改严格减少了正在完成的工作(以及内存需求)。
为了解决内存泄漏问题，我使用了一个本地虚拟节点，而不是动态分配它。这消除了最后一次使用new，从而消除了问题评论中提出的大多数反对意见。
Node* deleteAllOccurances(Node *head, int x)
{
Node new_head{-1}; //<-- Avoid dynamic allocation
new_head.next = head; //<-- added line
Node *tail = &new_head;
while(tail->next != nullptr) {
if(tail->next->data != x) {
tail = tail->next;
}
else { //<-- make the rest of the loop conditional
Node *q = tail->next;
tail->next = tail->next->next;
delete q;
}
}
return new_head.next;
}
此版本删除了"尴尬因素"，因为创建的一个节点有好处，并且没有使用new。这个版本足够干净，可以进行复杂性分析，而不会让每个人都问"为什么？？？"。