LeetCode 203:移除链表元素
删除链表中等于给定值 val 的所有节点。
Remove all elements from a linked list of integers that have value val.
示例:
输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
解题思路:
两种方法,一种是迭代法,从第一个节点开始,遇到值相同的节点就将其删除。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。
第二种方法是递归,用递归从后向前遇到相同节点直接指向该节点的下一个节点的地址即可
迭代法:
由于链表删除操作的特殊性,如果要删除某个节点,必须要知道该删除节点的前一个节点地址才可完成删除操作。所以如果是从第一个节点开始判断,就要考虑到第一个节点是否为空节点、第一个节点是否就是该删除的的节点,删除头节点和非头节点的操作不一样,应单独实现删除操作。
如果原链表是这种形式:1->1->1->2
val=1
删除头节点后第二个节点置为头节点,但是第二个节点作为新的头节点依然需要删除,所以对头节点的操作应该是一个迭代过程。
另外一种方法就是新建一个虚拟节点,该虚拟节点下一个节点指向原链表头节点。这就无需考虑头节点是否为空、是否为待删除节点。如原链表为:1->1->1->2
val=1
,新建一个虚拟节点 -1 作为头节点:-1->1->1->1->2
val=1
,这时只需正常迭代删除即可,唯一要注意是返回节点不能是 head ,因为原链表的头节点如果是待删除节点,此时 head 节点已被删除并作为单独隔离出来的节点,并非链表内的一个节点。
Java:
class Solution { public ListNode removeElements(ListNode head, int val) { ListNode newHead=new ListNode(-1);//新建虚拟节点 newHead.next=head;//虚拟节点作为原链表的头节点 ListNode cur = newHead;//遍历节点的指针 while (cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next;//删除操作 } else { cur = cur.next; } } return newHead.next;//返回的头节点应当是虚拟节点的下一个节点 } }
Python3:
class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: newHead = ListNode(-1) newHead.next = head cur = newHead while cur.next: if cur.next.val == val: cur.next = cur.next.next else: cur = cur.next return newHead.next
递归法:
递归方法解该题很简单,基线条件是遇到空节点(最后一个节点),递归时只需将传递参数节点的下一个节点作为新的参数传给递归函数即可:
如原链表为: 1->2->6->3->4->5->6, val = 6
递归到空节点时最后一个递归函数返回null: 1->2->6->3->4->5->6->null
回到上一层递归函数内此时 head.next 得到返回节点 null
判断head为 6 删除,返回 head.next :1->2->6->3->4->5->null
回到上一层递归函数此时 head.next 得到上一层返回节点依然为null
判断head为 5 不删除,返回 head 为5:1->2->6->3->4->5->null
回到上一层递归函数此时 head.next 得到上一层返回节点 5
判断head为 4 不删除,返回 head 为4:1->2->6->3->4->5->null
回到上一层递归函数此时 head.next 得到上一层返回节点 4
..............
直到回到第一个递归函数为止返回头节点结束。
Java:
class Solution { public ListNode removeElements(ListNode head, int val) { if (head == null) return null;//基线条件 head.next = removeElements(head.next, val); if (head.val == val) { return head.next; } else { return head; } } }
Python3:
class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: if not head: return None head.next = self.removeElements(head.next, val) if head.val == val: return head.next else: return head
欢迎关注公众号一起学习:爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
一文了解JVM
一、什么是JVM JVM是Java Virtual Machine(Java 虚拟机)的缩写,JVM是一种用于计算设备的规范,它是一个虚构出来的计算机,是通过在实际的计算机上仿真模拟各种计算机功能来实现的。 Java语言的一个非常重要的特点就是平台无关性。而使用Java虚拟机是实现这一特点的关键。一般的高级语言如果要在不同的平台上运行,至少需要编译成不同的目标代码。而引入Java语言虚拟机后,Java语言在不同平台上运行时不需要重新编译。Java语言使用Java虚拟机屏蔽了与具体平台相关的信息,使得Java语言编译程序只需生成在Java虚拟机上运行的目标代码(字节码),就可以在多种平台上不加修改地运行。Java虚拟机在执行字节码时,把字节码解释成具体平台上的机器指令执行。这就是Java的能够“一次编译,到处运行”的原因。 二、JVM总体
- 下一篇
fetch的常见问题及其解决办法
摘要: 玩转fetch。 作者:wonyun 原文:fetch使用的常见问题及其解决办法 Fundebug经授权转载,版权归原作者所有。 首先声明一下,本文不是要讲解fetch的具体用法,不清楚的可以参考MDN fetch教程。 引言 说道fetch就不得不提XMLHttpRequest了,XHR在发送web请求时需要开发者配置相关请求信息和成功后的回调,尽管开发者只关心请求成功后的业务处理,但是也要配置其他繁琐内容,导致配置和调用比较混乱,也不符合关注分离的原则;fetch的出现正是为了解决XHR存在的这些问题。例如下面代码: fetch(url) .then(function(response) { return response.json(); }) .then(function(data) { console.log(data); }) .catch(function(e) { console.log("Oops, error"); }); 上面这段代码让开发者只关注请求成功后的业务逻辑处理,其他的不用关心,相当简单;也比较符合现代Promise形式,比较友好。 fetch是基...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS关闭SELinux安全模块
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Mario游戏-低调大师作品
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Windows10,CentOS7,CentOS8安装Nodejs环境
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS8编译安装MySQL8.0.19
- MySQL8.0.19开启GTID主从同步CentOS8