Java教程

每日一题 2021/11/02

本文主要是介绍每日一题 2021/11/02,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

力扣:237. 删除链表中的节点

难度 简单

题目描述:

请编写一个函数,用于 删除单链表中某个特定节点 。在设计函数时需要注意,你无法访问链表的头节点 head ,只能直接访问 要被删除的节点

题目数据保证需要删除的节点 不是末尾节点 。

示例 1:

image

输入:head = [4,5,1,9], node = 5
输出:[4,1,9]
解释:指定链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9

示例 2:

image

输入:head = [4,5,1,9], node = 1
输出:[4,5,9]
解释:指定链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9

示例 3:

输入:head = [1,2,3,4], node = 3
输出:[1,2,4]

示例 4:

输入:head = [0,1], node = 0
输出:[1]

示例 5:

输入:head = [-3,5,-99], node = -3
输出:[5,-99]

提示:

  • 链表中节点的数目范围是 [2, 1000]
  • \(-1000\) <= Node.val <= \(1000\)
  • 链表中每个节点的值都是唯一的
  • 需要删除的节点 node链表中的一个有效节点 ,且 不是末尾节点

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-node-in-a-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

根据一般思路,如果要删除链表中的结点,需要进行一下三步操作:

  1. 找到前置结点 pre
  2. 将前置结点的 next 设置为目标结点的 next
  3. 删除目标结点。

但是这个题目却只给出目标结点,没有给出链表头结点 head ,所以只能换一种思路。

如果将题目中的实例的图进行改变的话,就可以得出一个新的思路,以示例 1为例

image

通过这个图就可以得到一个新的思路:

  1. 将目标结点修改为 next 结点。
  2. 删除 next 结点。

代码实现如下:

/**
 * 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 = node->next->val;
        node->next = node->next->next;
        delete p;
    }
};

用时和内存的情况是8ms/7.5MB,超过了89.488%/62.971%

再来看看双百的答案:

/**
 * 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) {
            node->val=node->next->val;
            node->next=node->next->next;
    }
};

可以发现双百的答案少了一个删除 next 结点的操作,因此时间更快,空间更少。但是这种操作只能在这种题目之中使用。因为如果在项目之中使用了链表等结构的话,如果删除操作只是改变其它数据,而没有对原数据的内存释放,会发生内存泄露(其实这些小型程序也发生了内存泄露,但是马上就找回来了),是非常重大的错误,所以要养成 deletefree 的习惯

参考链接:为什么有的C++程序new之后,却不delete呢?或者说,new之后,由于需要不想delete怎么办? - SegmentFault 思否

这篇关于每日一题 2021/11/02的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!