在O(1)时间删除链表结点

题目 在O(1)时间删除链表结点

思路分析

单链表不方便找前驱节点，所以我们不能按常规方法将该节点删除。

可以换一种思路，将下一个节点的值复制到当前节点，然后将下一个节点删除即可。

“借尸还魂”

代码实现

 /**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    void deleteNode(ListNode* node) {

        auto p = node->next;

        node->val = p->val;

        node->next = p->next;

        // 这两步的作用就是将 *(node->next) 赋值给 *node，所以可以合并成一条语句：

        // *node = *(node->next);

        delete p;

    }

};

同类题型

视频讲解

⬅️ 圆圈中最后剩下的数字 🏠 00-刷题理模型 ➡️ 春晚刘谦魔术 约瑟夫问题