【力扣算法17】之 19. 删除链表的倒数第 N 个结点 python

简介: 【力扣算法17】之 19. 删除链表的倒数第 N 个结点 python

问题描述

给你一个链表,删除链表的倒数第 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

思路分析

  1. 首先,我们需要删除链表的倒数第n个节点。为了能够找到要删除的节点,我们需要知道链表的长度。
  2. 我们可以通过遍历链表来获取链表的长度。假设链表的长度为length
  3. 然后,我们可以根据链表的长度和要删除的节点的位置,计算出要删除的节点在正向遍历中的位置。假设要删除的节点在正向遍历中的位置为pos
  4. 接下来,我们需要找到要删除的节点的前一个节点,即倒数第n+1个节点。根据第3步计算的位置,我们可以通过遍历链表来定位到该节点。
  5. 最后,将要删除的节点从链表中移除,即将前一个节点的next指针指向下一个节点。

这个思路的关键点是使用双指针的技巧。通过快指针先向前移动n步,可以使得快指针和慢指针之间相差n个节点。然后同时移动快指针和慢指针,直到快指针到达链表的末尾。这样,慢指针所指向的节点就是要删除的节点的前一个节点。

通过这种方法,我们可以在一次遍历中找到要删除的节点的前一个节点,并进行删除操作,而不需要遍历两次链表来实现。


代码分析

  1. 创建一个虚拟头结点 dummy,并将它指向原链表的头结点 head
  2. 定义两个指针 fastslow,初始时都指向虚拟头结点。
  3. 快指针 fast 先向前移动 n 步,即 for i in range(n+1): fast = fast.next
  4. 同时移动快指针和慢指针,直到快指针 fast 到达链表的末尾。使用循环 while fast:,循环内部的操作为 fast = fast.nextslow = slow.next
  5. 此时,慢指针 slow 所指向的节点就是要删除的节点的前一个节点。
  6. 将慢指针 slow 所指向的节点的 next 指针指向下一个节点的 next 指针,即 slow.next = slow.next.next,实现删除倒数第 n 个节点。
  7. 返回 dummy.next,即为新链表的头结点。

完整代码

class Solution(object):
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)  # 创建一个虚拟头结点,值为0
        dummy.next = head  # 将虚拟头结点指向原链表的头结点
        fast = dummy  # 快指针初始指向虚拟头结点
        slow = dummy  # 慢指针初始指向虚拟头结点
        for i in range(n+1):  # 快指针先向前移动n步(包括虚拟头结点)
            fast = fast.next
        while fast:  # 同时移动快指针和慢指针,直到快指针到达链表末尾
            fast = fast.next  # 快指针每次移动一步
            slow = slow.next  # 慢指针每次移动一步
        slow.next = slow.next.next  # 删除倒数第n个节点,将慢指针指向的节点的next指针指向下一个节点的next指针
        return dummy.next  # 返回链表的头结点

详细分析


class Solution(object):
• 1

定义一个名为Solution的类。

def removeNthFromEnd(self, head, n):
• 1

定义了一个名为removeNthFromEnd的方法,该方法接受两个参数:head表示链表的头结点,n表示要删除的倒数第n个节点。

dummy = ListNode(0)
• 1

创建一个名为dummy的虚拟头结点,值为0。

dummy.next = head
• 1

将虚拟头结点的next指针指向原链表的头结点,以便建立虚拟头结点与原链表的连接。

fast = dummy
        slow = dummy

初始化快指针fast和慢指针slow,都指向虚拟头结点。

for i in range(n+1):
            fast = fast.next

快指针先向前移动n步(包括虚拟头结点),以建立快慢指针之间的n个节点的距离。

while fast:
            fast = fast.next
            slow = slow.next

同时移动快指针和慢指针,快指针每次向前移动一步,慢指针每次向前移动一步,直到快指针到达链表末尾。

slow.next = slow.next.next
• 1

删除倒数第n个节点,即将慢指针指向的节点的next指针指向下一个节点的next指针。通过跳过要删除的节点实现删除操作。

return dummy.next
• 1

返回链表的头结点,即虚拟头结点的下一个节点,用于处理删除头结点的情况。


运行效果截图


完结

目录
打赏
0
0
0
0
25
分享
相关文章
Python 实现单向链表,和单向链表的反转
链表是一种数据结构,每个节点存储相邻节点的位置信息。单链表中的节点仅存储下一节点的位置。通过Python实现单链表,定义`ListNode`类并关联节点可创建链表。例如,创建A-&gt;B-&gt;C的链表后,可通过反转函数`reverse`将链表反转为CBA。代码展示了如何实现和操作单链表。
Python 实现单向链表,和单向链表的反转
Python 实现反转、合并链表有啥用?
大家好,我是V哥。本文介绍Python实现反转链表和合并链表的应用场景及代码实现。反转链表适用于时间序列数据展示、回文链表判断等;合并链表则用于大规模数据排序、数据库查询结果集合并等。通过迭代和递归方法实现反转链表,以及合并两个或多个有序链表的算法,帮助开发者解决实际问题。关注V哥,了解更多实用编程技巧。 先赞再看后评论,腰缠万贯财进门。
|
3月前
|
探索 Python 中链表的实现:从基础到高级
链表是一种由节点组成的基础数据结构,每个节点包含数据和指向下一个节点的引用。本文通过Python类实现单向链表,详细介绍了创建、插入、删除节点等操作,并提供示例代码帮助理解。链表在处理动态数据时具有高效性,适用于大量数据变动的场景。文章为初学者提供了全面的入门指南,助你掌握链表的核心概念与应用。
106 0
|
8月前
|
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
41 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
8月前
|
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
78 5
|
8月前
|
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
69 4
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
8月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
84 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
174 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
127 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等