经典链表题:删除倒数第 N 个节点|Java 刷题打卡

简介: 经典链表题:删除倒数第 N 个节点|Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 19. 删除链表的倒数第 N 个结点 ,难度为 中等


Tag : 「链表」、「快慢指针」、「双指针」


给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。


进阶:你能尝试使用一趟扫描实现吗?


示例 1:



网络异常,图片无法展示
|


输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
复制代码


示例 2:


输入:head = [1], n = 1
输出:[]
复制代码


示例 3:


输入:head = [1,2], n = 1
输出:[1]
复制代码


提示:


  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz


快慢指针



删除链表的倒数第 n 个结点,首先要确定倒数第 n 个节点的位置。


我们可以设定两个指针,分别为 slowfast,刚开始都指向 head。


然后先让 fast 往前走 n 步,slow 指针不动,这时候两个指针的距离为 n


再让 slowfast 同时往前走(保持两者距离不变),直到 fast 指针到达结尾的位置。


这时候 slow 会停在待删除节点的前一个位置,让 slow.next = slow.next.next 即可。


但这里有一个需要注意的边界情况是:如果链表的长度是 L,而我们恰好要删除的是倒数第 L 个节点(删除头节点),这时候 fast 往前走 n 步之后会变为 null,此时我们只需要让 head = slow.next 即可删除。


代码:


class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (n-- > 0) fast = fast.next;
        if (fast == null) {
            head = slow.next;
        } else {
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
            slow.next = slow.next.next;
        }
        return head;
    }
}
复制代码


  • 时间复杂度:需要扫描的长度为链表的长度。复杂度为 O(n)O(n)
  • 空间复杂度:O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.19 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
5月前
|
Java 区块链 网络架构
酷阿鲸森林农场:Java 区块链系统中的 P2P 区块同步与节点自动加入机制
本文介绍了基于 Java 的去中心化区块链电商系统设计与实现,重点探讨了 P2P 网络在酷阿鲸森林农场项目中的应用。通过节点自动发现、区块广播同步及链校验功能,系统实现了无需中心服务器的点对点网络架构。文章详细解析了核心代码逻辑,包括 P2P 服务端监听、客户端广播新区块及节点列表自动获取等环节,并提出了消息签名验证、WebSocket 替代 Socket 等优化方向。该系统不仅适用于农业电商,还可扩展至教育、物流等领域,构建可信数据链条。
|
11月前
|
分布式计算 Java MaxCompute
ODPS MR节点跑graph连通分量计算代码报错java heap space如何解决
任务启动命令:jar -resources odps-graph-connect-family-2.0-SNAPSHOT.jar -classpath ./odps-graph-connect-family-2.0-SNAPSHOT.jar ConnectFamily 若是设置参数该如何设置
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
12月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
84 3
|
12月前
|
分布式计算 资源调度 Hadoop
大数据-01-基础环境搭建 超详细 Hadoop Java 环境变量 3节点云服务器 2C4G XML 集群配置 HDFS Yarn MapRedece
大数据-01-基础环境搭建 超详细 Hadoop Java 环境变量 3节点云服务器 2C4G XML 集群配置 HDFS Yarn MapRedece
299 4
|
12月前
|
分布式计算 Java Hadoop
Hadoop-30 ZooKeeper集群 JavaAPI 客户端 POM Java操作ZK 监听节点 监听数据变化 创建节点 删除节点
Hadoop-30 ZooKeeper集群 JavaAPI 客户端 POM Java操作ZK 监听节点 监听数据变化 创建节点 删除节点
199 1
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
132 2
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
170 1

热门文章

最新文章