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

2018-08-06 3319

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

题目：

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