算法题学习 --- 删除链表的倒数第 n 个节点
题目
描述
给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针 例如，
给出的链表为: 1→2→3→4→5, n= 2. 删除了链表的倒数第 n 个节点之后,链表变为 1→2→3→5.
数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(n) 备注：
题目保证 n 一定是有效的
示例 1
分析
考虑特殊情况
在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？
不难发现，如下情况：
如果输入的头结点为空，那么返回 nullptr 即可
考虑一般情况
这个问题实际上是在寻找链表倒数第 n 个节点的基础上引入的，
寻找链表的第 n 个节点的方式：
假设链表长度为 length，我们需要知道怎么才能走 length-n 步，这样考虑，我们设置快慢指针，快指针先走 n 步，然后慢指针再和快指针一起走，这样，当快指针走到链表末尾时，慢指针恰好走了 length-n 步，也就直接返回慢指针的节点就好了。
也就是说我们要先找到倒数第 n 个节点，然后同时记录它的前驱节点，然后做删除节点的操作即可，如下：
step 1：给链表添加一个表头，处理删掉第一个元素时比较方便。
step 2：准备一个快指针，在链表上先走 n 步。
step 3：准备慢指针指向原始链表头，代表当前元素，前序节点指向添加的表头，这样两个指针之间相距就是一直都是 n。
step 4：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数 n 个元素的位置。
step 5：最后将该节点前序节点的指针指向该节点后一个节点，删掉这个节点。
代码示例
注意，这里我们增加了一个链表头 pReturn，避免需要删除头结点的情况；
使用 pPre 不断记录 pSlow 的前驱，以便后面删除 pSlow 节点。
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/bd3b7919ad910993a71ec1866】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论