《剑指offer刷题笔记》16、在O(1)时间删除链表结点【c++详细题解】

川长思鸟来 2021-07-24 11:31 262阅读 0赞

### **题目** ###

给定单向链表的一个节点指针，定义一个函数在 O ( 1 ) O(1) O(1)时间删除该结点。

假设链表一定存在，并且该节点一定不是尾节点。

**样例**

输入：链表 1->4->6->8
          删掉节点：第2个节点即6（头节点为第0个节点）
    
    输出：新链表 1->4->8

### **思路** ###

**(链表)**  O ( 1 ) O(1) O(1)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70][]

由于是单链表，我们不能找到前驱节点，所以我们不能按常规方法将该节点删除。  
我们可以换一种思路，将下一个节点的值复制到当前节点，然后将下一个节点删除即可。

**时间复杂度**

只有常数次操作，所以时间复杂度是  O ( 1 ) 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) { 
            ListNode* p = node->next;  //当前节点的下一个结点
            node->val = p->val;  //将下一个节点的值复制到当前节点
            node->next = p->next; //将下一个节点删除即可
            delete p;//防止内存泄露
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/9b19b5948dc0478a9cbb5a84ee73cd82.png