开发面试题 nginx反向代理 overflow 软件开发 swing hive automation lua vue注册组件 vue配置 idea返回值快捷键 vm虚拟化引擎 git登陆命令 kali重启网卡 xshell搭建ss matlab读入图片 mysql建表主键自增长 mysql入门 python中time python中的join函数 java入门 java实现接口 java课程 java中class java方法的调用 unix系统下载 js延迟加载的方式 bbm注册 原创检测工具 正当防卫4存档 头条视频解析 深入解析windows操作系统 屏幕录像专家注册机 jsp源码下载 bin文件编辑器 黑道圣徒4去马赛克补丁 dnf卡邮件 刻刀工具 xfce4 python列表去重
当前位置: 首页 > 学习教程  > 编程语言

JZO#18:删除链表的节点

2020/11/24 11:17:38 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述: 给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。 注意:此题对比原题有改动 示例 1: 输入: head [4,5,1,9], val 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点…

题目描述:

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

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

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

说明:

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言,你不需要 free 或 delete 被删除的节点

 

解题方法:

原题目要求在O(1)的时间内完成删除,基本思路是将待删除结点的下一节点内容覆盖待删除节点,然后删除下一节点。这一思路需要解决几个特殊情况:

  • 删除头节点,那么原来的头节点head会发生改变。
  • 删除尾节点,那么没有下一个节点的内容可以拷贝,仍然需要从头寻找待删除节点的上一节点,修改next。
  • 需要删除的节点不在链表中,需要遍历链表才能够确定这一情况。时间O(n)。

这一题目对于时间复杂度没有要求,所以最终还是采用了传统的O(n)时间方法进行完成。

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (head == nullptr) {
            return head;
        }

        ListNode* toDel = head;
        ListNode* preNode = nullptr;
        while(toDel != nullptr && toDel->val != val) {
            preNode = toDel;
            toDel = toDel->next;
        }

        if(toDel == nullptr) {
            toDel = nullptr;
            preNode = nullptr;
            return head;
        } else if (toDel == head) {
            head = head->next;
            //delete toDel;
            toDel = nullptr;
            preNode = nullptr;
            return head;
        } else {
            preNode->next = toDel->next;
            //delete toDel->next;
            toDel = nullptr;
            preNode = nullptr;
            return head;
        }
    }
};

 


本文链接: http://www.dtmao.cc/news_show_400442.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?