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

  1. 云栖社区>
  2. 小詹学Python>
  3. 博客>
  4. 正文

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

技术小能手 2018-08-06 13:46:19 浏览2937
展开阅读全文

题目:

给定一个链表,删除链表的倒数第 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 。之后两个指针同步后移 ,当先移动的指针指到最后的时候 ,第二个指针进行跳过删除操作 ,即可实现目的 。

image

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

image

原文发布时间为:2018-08-06
本文作者:小詹同学
本文来自云栖社区合作伙伴“小詹学Python”,了解相关信息可以关注“小詹学Python

网友评论

登录后评论
0/500
评论
技术小能手
+ 关注
所属团队号: 小詹学Python