剑指offer 16. 在O(1)时间删除链表结点

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

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

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

数据范围

链表长度 [1,500]。

样例

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

输出：新链表 1->4->8
1
2
3
4

方法一：链表 O(1)

这道题删除结点要用 O(1) 的时间复杂度，所以我们可以直接将删除结点的下一个结点复制给该删除结点即可。

第一步： 我们要删除的是结点 node ，所以我们可以用另一个指针 p 指向 node 的下一个结点。

第二步： 将 p 所指向结点的值赋值给 node 所指向的结点，然后将 node 指向的下一个结点指向 next1 的下一个结点。

/**
 * 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;
        delete[]p;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

欢迎大家在评论区交流~