图解LeetCode——19. 删除链表的倒数第 N 个结点

简介: 图解LeetCode——19. 删除链表的倒数第 N 个结点

一、题目

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

二、示例

2.1> 示例 1:

输入】head = [1,2,3,4,5], n = 2

输出】[1,2,3,5]

2.2> 示例 2:

输入】head = [1], n = 1

输出】[]

2.3> 示例 3:

输入】head = [1,2], n = 1

输出】[1]

提示:

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

进阶:

  • 你能尝试使用一趟扫描实现吗?

三、解题思路

根据题目描述,我们要去删除倒数第N个节点,那么由于该链表的单向性,我们可以通过遍历先计算整个链表中的节点的个数,比如一共有6个节点,那么如果要删除倒数第3个节点的话,我们其实就是要删除从头结点开始计算的第4个节点,这样就可以完成题意了。

但是在题目给出的进阶部分,它提出我们能否尝试使用一趟扫描实现吗?那么上面的解题思路就不适合这种要求了。我们可以采用双指针(p1p2)的方式,即:还是以一共有6个节点,我们要删除倒数第3个节点为例。为了方便起见,我们可以创建一个虚拟节点,然后放到整个链表的头部,这样加入要删除倒数第6个节点,即:头结点的话,我们也更方便操作。

那么由于要删除倒数第3个节点,我们可以先让p2向后执行3步,这样,p1与p2步数之差就是3步了。然后我们同时让p1和p2都一步一步的向链表的末尾移动,当p2指向了链表中的最后一个节点的时候,我们就可以停止p1与p2的移动操作了。那么此时我们会发现p1指向的节点正好是倒数第4个节点,而p1.next就是我们要删除的节点。那么删除操作就非常容易了,即:p1.next = p1.next.next

以上就是解题思路了,为了便于理解,我们以输入head = [1,2,3,4,5,6], n = 3为例,看一下具体的操作过程。具体操作流程,请见下图所示:

四、代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = new ListNode(-1);
        temp.next = head;
        ListNode p1 = temp, p2 = temp;
        while(n-- > 0) {
            p2 = p2.next;
        }
        while (p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return temp.next;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

相关文章
|
19天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
31 1
|
25天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
44 0
Leetcode第21题(合并两个有序链表)
|
23天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
57 1
|
5天前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
6 1
|
25天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
14 0
LeetCode第二十四题(两两交换链表中的节点)
|
25天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
37 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
19天前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
36 0
|
25天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
65 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2