专栏首页desperate633LeetCode Remove Linked List Elements

LeetCode Remove Linked List Elements

Remove all elements from a linked list of integers that have value val. Example*****Given:* 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6Return: 1 --> 2 --> 3 --> 4 --> 5 Credits:Special thanks to @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question.

描述:

删除链表中等于给定值val的所有节点。

样例:

给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5。

** 分析: **

1.首先判断head是不是空,为空就直接返回null 2.然后从head.next开始循环遍历,删除相等于val的元素 3.最后判断head是否和val相等,若相等,head = head.next (这里最后判断head是有原因的,因为head只是一个节点,只要判断一次,如果最先判断head就比较麻烦,因为如果等于val,head就要发生变化) 这里也体现出为什么设计链表的时候要空出一个头结点

** 代码 **:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        
        //边界条件判断,如果head为null,则直接返回null
        if(head == null)
            return null;
        
        //操作链表时的技巧,为了方便返回结果,我们新建一个dummy节点作为一个头结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //删除链表时的操作,最好加一个头结点,这样删除的操作就是:head.next = head.next.next
        head = dummy;
        
        //开始循环链表,结束的条件是到达最后一个节点,因为有一个头结点的存在,所以是head.next != null
        while(head.next != null) {
            //如果head.next节点等于val,就是要被删除的节点
            if(head.next.val == val)
                head.next = head.next.next;
            //否则继续判断下一个节点
            else
                head = head.next;
        }
        return dummy.next;
        
    }
}

Paste_Image.png

在leetcode的讨论中,看到一个特别的方法,三行递归代码解决这个问题: 首先我们先看代码:

public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
}

思路比较新颖,但原理很简单,递归调用,如果当前节点等于val就删除,但是效率较低,但不失为拓展思路的好方法,或许链表的结构也利于使用递归?

Paste_Image.png

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 肖风:从这5个方向入手,全方位读懂区块链?

    阅读本文前请先思考: 区块链的核心和本质是什么? 去中心化的逻辑是什么? 2018年区块链的发展处于什么阶段?

    辉哥
  • Git_学习_00_资源帖

    3.Git简明教程 : https://rdc.hand-china.com/gitlab/HAP/hap-developer-guide/blob/maste...

    shirayner
  • Facebook 宣布开源 Katran,高性能第4层负载平衡器

    为了管理Facebook的流量,他们部署了一个分布式PoP服务器作为数据中心的代理。鉴于极高的请求量,PoP和数据中心都面临着巨大挑战,比如如何将大量的后端服务...

    后端技术探索
  • 再说TCP神奇的40ms

    TCP是一个复杂的协议,每个机制在带来优势的同时也会引入其他的问题。 Nagel算法和delay ack机制是减少发送端和接收端包量的两个机制, 可以有效减少网...

    后端技术探索
  • 白话AI

    过去我们用通过编写设定程序来直接让计算机完成某些特定任务,现在,我们还可以训练计算机,就像我们训练宠物一样。这就是用大白话来解释机器学习。当然了,对于一些相对简...

    后端技术探索
  • JavaUtil_01_MD5加密

    昨天做java微信开发,引用百度翻译API给公众号添加翻译功能时,需要使用MD5生成签名。注意,使用MD5生成签名后一定要转成小写,不然百度翻译后台不会认你这个...

    shirayner
  • 八大排序算法稳定性分析,原来稳定性是这个意思...

    2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

    谭庆波
  • 有效解决VC++6.0一个工程不能有多个main函数的解决方案

    现象:在一个工程中有2个带有main函数的文件:InsertSort.cpp,ShellSort.cpp

    shirayner
  • 有哪些实用且堪称神器的Chrome插件?吐血推荐!!!

    相信很多人都在使用 Chrome 浏览器,其流畅的浏览体验得到了不少用户的偏爱,但流畅只是一方面, Chrome 最大的优势还是其支持众多强大好用的扩展程序(E...

    谭庆波
  • 业务id转密文短链的一种实现思路

    买家通过电商app下单后,会受到一条短信,短信内容中包括改订单详情页面的h5地址连接,因为是出现在短信中,所以对连接有要求:1.尽量短;2.安全性考虑,订单在数...

    后端技术探索

扫码关注云+社区

领取腾讯云代金券