删除链表的倒数第 N 个结点
除 倒数第 n 个 节点,所以首先得找到 该节点的前一节点 ,但由于不知道 整个链表的长度,因此不知道 待删除的节点是正数的第几个节点,所以很难从头节点开始遍历时删除掉这个节点。 思路一 先遍历一遍链表,获取整个链表的长度;假设整个链表的长度为 l,则可知要删除的节点为第 l - n + 1 个节点;再遍历一遍,删除倒数第 n 个节点。例如链表 L 为 1->2->3->4->5,n = 3,则要删除的节点为 第 5 - 3 + 1 = 3 个节点 。 思路二 尽管思路一可行,但是需要 遍历链表两遍,不够简洁,而且题目的 进阶 中也提到尝试使用一趟扫描实现,因此本文采用 双指针 的策略,实现通过一次扫描删除 倒数第 n 个节点 。 在上一期链表相关专题 虚拟头节点秒杀链表问题 中提到 增加虚拟头节点 的策略解决链表问题,增加虚拟头节点的 好处 在于:不需要单独考虑头节点,这样对头节点的处理就像跟其它节点一样。本文也同样采用这种策略。此时 fast 跟 slow 之间的间距是固定(n = 3)的,找到 target(slow)后,只需要删除其下一节点即可,但 slow 指向的节点前面有多少个节点该如何确定呢?
由于当前已知 fast 和 slow 指向节点之间的长度是固定的,只需要将这两个指针向前挪,直到 slow 挪到虚拟头节点(值为 0)的位置,此时 fast 指向值为 4 的节点的位置,fast 只需要由虚拟头节点的位置 右移 n + 1 = 4 即可。如下图示: (编辑:开发网_郴州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |