"链表删除操作优化"
在链表数据结构中，删除一个节点通常涉及到遍历链表来找到目标节点，然后修改其前驱节点的next指针以实现删除。然而，如果已知链表的头指针和要删除的节点的指针，我们可以实现一个在O(1)时间复杂度内删除该节点的方法。这道题目要求在常数时间内完成删除操作，关键在于利用已有的目标节点指针。
首先，我们来看一下标准的链表删除过程。假设我们有一个链表节点结构`ListNode`：
```cpp
struct ListNode {
int m_nKey;
ListNode* m_pNext;
};
```
通常，删除节点`node`的步骤如下：
1. 使用两个指针`q`和`pre`，`q`用于遍历链表，`pre`始终指向`q`的前一个节点。
2. 当`q`等于要删除的节点`node`时，更新`pre->next = q->next`，然后释放`q`所指向的内存，即`delete q`。
但这种方法的时间复杂度是O(n)，因为它需要遍历链表找到目标节点。
题目要求在O(1)时间复杂度内删除节点，由于我们已经有了要删除节点`pToBeDeleted`的指针，可以直接操作。删除节点的关键在于不直接改变`pToBeDeleted`，而是改变它前面的节点。这里可以采用以下策略：
1. 如果`pToBeDeleted`不是链表的最后一个节点，将`pToBeDeleted`的下一个节点`p`的值复制到`pToBeDeleted`中，然后设置`pToBeDeleted->next = p->next`，最后删除`p`。这样，从链表的其他部分看，`pToBeDeleted`已经被删除，实际上我们只是删除了`p`。
2. 如果`pToBeDeleted`是链表的最后一个节点，由于没有后续节点，我们需要按照传统方式遍历链表找到它的前一个节点，然后执行上述步骤。
以下是实现这个操作的C++代码：
```cpp
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted) {
if (pToBeDeleted->m_pNext != NULL) { // 不是最后一个节点
pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey;
pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;
free(pToBeDeleted->m_pNext); // 删除pToBeDeleted后面的节点p
} else { // 最后一个节点
ListNode* pre = pListHead;
while (pre->m_pNext != pToBeDeleted) {
pre = pre->m_pNext;
}
pre->m_pNext = NULL; // 将pre的next设为NULL，表示删除了pToBeDeleted
}
}
```
这段代码首先检查`pToBeDeleted`是否为最后一个节点，如果不是，则直接交换其值和下一个节点的值，并删除下一个节点；如果是最后一个节点，就需要遍历链表找到前一个节点并进行相应操作。
这个方法充分利用了已知目标节点的指针，避免了遍历链表的过程，从而实现了O(1)时间复杂度的删除操作。注意，这里的O(1)是指删除操作本身的时间复杂度，不包括寻找最后一个节点的情况，因为后者仍需线性时间。
我的内容管理
展开
