《程序员面试金典（第6版）》面试题 02.03. 删除中间节点

题目描述

若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。

假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。

例如：
传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

示例：

• 输入：节点 5 （位于单向链表 4->5->1->9 中）
  输出：不返回任何数据，从链表中删除传入的节点 5，使链表变为 4->1->9

解题思路与代码

这道题其实就给了我们一个要被删除的节点，给的不是链表的头节点。第一开始我做这道题时，还想了想，删除节点的一般操作不就是要找到删除节点的前驱节点嘛？这怎么找前驱节点。然后我就想了一个法子，把要删除节点的后一个节点的值，去覆盖前一个节点的值，然后依次覆盖，最后把最后一个节点扔掉就可以。 具体看代码，这里就不多赘述了。

class Solution {
public:void deleteNode(ListNode* node) {ListNode* pos = node->next;while(pos->next != nullptr){node->val = pos->val;node = pos;pos = pos->next;}node->val = pos->val;node->next = nullptr;}
};

复杂度分析：
时间复杂度 O(n)，n是链表的长度，因为使用了while循环语句
空间复杂度O(1)

后面我又想，我干嘛去扔最后一个节点呢？我直接将要删除的节点后一个的值拷贝到要删除节点上，然后将要删除节点的指针指向它下一个的下一个不就好了么？这不就是变相的扔掉了删除节点的后一个节点嘛？

class Solution {
public:void deleteNode(ListNode* node) {node->val = node->next->val;node->next = node->next->next;}
};

复杂度分析：
时间复杂度：O(1)
空间复杂度:O(1)

总结

这道题其实就是一道阅读理解的题。给你删除节点，那你直接在原地操作就可以了。不要再想着变量链表。