O(1)时间复杂度删除链表节点的解决方案

"链表删除操作优化" 在链表数据结构中，删除一个节点通常涉及到遍历链表来找到目标节点，然后修改其前驱节点的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)是指删除操作本身的时间复杂度，不包括寻找最后一个节点的情况，因为后者仍需线性时间。