Leetcode打卡 | No.19 删除链表的倒数第N个节点

No.19 删除链表的倒数第N个节点

题目:

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

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


之前我们说过 C 和 C++ 中的指针是个好东西 ,在解决这类问题很是方便 。然而 python 是没有这个概念的 ,包括链表也是模拟链表的相关操作 。刷题到这 ,小詹也得考虑总结下 python 中链表的相关操作了 。

思路一 :首先利用一次循环得到链表长度 ,之后根据题目输入的参数在指定位置进行删除操作 ,即要删除第 L-n+1 个节点 ,只需要将第 L-n 个节点的指针指向第 L-n+2 个节点即可跳过要删除的节点 。(在第 L-n+2 个节点存在的情况下 ,不存在即要删除倒数第一个节点 ,是个特例情况 。)

思路二:这里考虑用两个 ‘指针’ 进行操作 ,要删除倒数第 n 个节点 ,即与最后一个节点的间隔是固定的 (n-1)。这里先将两个指针同时指向头结点 ,然后第一个指针后移对应位置 ,使得两个指针间隔为 n-1 。之后两个指针同步后移 ,当先移动的指针指到最后的时候 ,第二个指针进行跳过删除操作 ,即可实现目的 。

说点题外话 ,leetcode 提交同一个代码会有一定的时间偏差 ,比如这个代码就在40-60 ms之间 ,导致得到的结果偏差很大 。小詹比较要脸 ,就放一个相对 beat 比较多的结果出来哈哈 。

原文发布于微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文发表时间:2018-08-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

在Scala里面如何使用正则处理数据

3365
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版6.7节多继承

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

921
来自专栏书山有路勤为径

1.C与C++

使用c++中的标准库类型vector可以很轻松的完成任务。 不需要管理内存分配,对不同的类型都可以处理

1324
来自专栏python3

python3--列表推导式,生成器表达式,内置函数

3,python不但使用迭代器协议,让for循环变得更加通用,大部分内置函数,也是使用迭代器协议访问对象的,例如sum函数是python的内置函数,该函数使用迭...

5990
来自专栏平凡文摘

7大经典的排序算法总结实现

1442
来自专栏韦弦的偶尔分享

Swift 两个数组的交集 II - LeetCode

给定两个数组,写一个方法来计算它们的交集。 例如: 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

2962
来自专栏专注研发

排序概述

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

1042
来自专栏小樱的经验随笔

洛谷 P1308 统计单词数【字符串+模拟】

P1308 统计单词数 题目描述 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。 现在...

3335
来自专栏数据小魔方

左手用R右手Python系列之——迭代器与迭代对象

接触过Python的小伙伴儿肯定都知道,Python中关于迭代器和可迭代对象运用的很广泛。迭代器可以以一种非常友好的方式使用在循环中,不仅节省内存,还能优化代码...

3838
来自专栏菩提树下的杨过

python:函数的高级特性

2233

扫码关注云+社区

领取腾讯云代金券