力扣题目 19:删除链表的倒数第N个节点 【python】

简介: 力扣题目 19:删除链表的倒数第N个节点 【python】

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区作者专栏每日更新:

image.png

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

示例

给定一个链表: 1->2->3->4->5, 和 n = 2.
 
当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明

给定的 n 保证是有效的。

进阶

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

解题思路

解决这个问题的关键是找到倒数第 n+1 个节点。我们可以使用两个指针 firstsecond 同时对链表进行遍历,并且 firstsecond 超前 n+1 步。当 first 遍历到链表末尾时,second 将指向倒数第 n+1 个节点。然后我们就可以调整 secondnext 指针来删除倒数第 n 个节点。

代码实现

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    
    # 移动 first,使得 first 和 second 之间相隔 n+1 个节点
    for _ in range(n + 1):
        first = first.next
    
    # 同时移动 first 和 second,直到 first 指向链表末尾
    while first is not None:
        first = first.next
        second = second.next
    
    # 删除倒数第 n 个节点
    second.next = second.next.next
    
    return dummy.next

算法分析

  • 时间复杂度:O(L),其中 L 是链表的长度。算法对链表进行了一次遍历。
  • 空间复杂度:O(1),只用了常数级别的额外空间。

算法图解

初始状态

  • 假设链表为 1 -> 2 -> 3 -> 4 -> 5n = 2,目标是删除倒数第二个节点,即节点 4
  • 我们引入一个哑节点(dummy node)作为链表的新头节点,这样可以方便地处理边界情况,比如删除头节点。

表示链表的表格如下:

添加双指针

  • 设置两个指针 firstsecond,初始时都指向哑节点。

移动 first 指针

  • first 指针向前移动 n + 1 步,使得 firstsecond 之间相隔 n 个节点。

同时移动 firstsecond 指针

  • 同时移动 firstsecond 指针,直到 first 指向链表末尾的空节点。此时,second 将指向倒数第 n + 1 个节点。

删除倒数第 N 个节点

  • 调整 secondnext 指针,使其指向倒数第 n 个节点的下一个节点,从而删除倒数第 n 个节点。

结果

删除节点 4 后的链表为:1 -> 2 -> 3 -> 5

通过这种方法,我们只需要一趟扫描就能找到倒数第 n 个节点的位置,并进行删除操作,达到高效解决问题的目的。

结论

通过使用双指针的方法,我们可以高效地解决删除链表倒数第 N 个节点的问题,这个技巧在链表问题中非常实用,值得掌握。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
2天前
|
机器人 Shell 开发者
`roslibpy`是一个Python库,它允许非ROS(Robot Operating System)环境(如Web浏览器、移动应用等)与ROS环境进行交互。通过使用`roslibpy`,开发者可以编写Python代码来远程控制ROS节点,发布和订阅话题,以及调用服务。
`roslibpy`是一个Python库,它允许非ROS(Robot Operating System)环境(如Web浏览器、移动应用等)与ROS环境进行交互。通过使用`roslibpy`,开发者可以编写Python代码来远程控制ROS节点,发布和订阅话题,以及调用服务。
19 8
|
15天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
14 2
|
15天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
10 1
|
15天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
12 1
|
5天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
5天前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
1月前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
15天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
10 0
|
15天前
|
SQL 分布式计算 DataWorks
DataWorks产品使用合集之在依赖普通的Python脚本和开源第三方包的场景下,如何使用DataWorks PyODPS节点调用第三方包
DataWorks作为一站式的数据开发与治理平台,提供了从数据采集、清洗、开发、调度、服务化、质量监控到安全管理的全套解决方案,帮助企业构建高效、规范、安全的大数据处理体系。以下是对DataWorks产品使用合集的概述,涵盖数据处理的各个环节。
34 0
|
25天前
|
Python
用python写单链表
用python写单链表