TBLEG
扫描微信账号

扫一扫微信二维码

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

2020-05-16 信息
区块链白皮书代写 题目:

给定一个链表,删除链表倒数第 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 比较多结果出来哈哈 。

全文阅读
文章关键词
云栖社区
c++
python
Image
同步
扫描关注微信账号

试试长按二维码加关注