每日：删除链表倒数第 N 个结点

本文转载自微信公众号「三分钟学前端」，每日作者sisterAn。删除转载本文请联系三分钟学前端公众号。链表

给定一个链表，倒数第N点删除链表的个结倒数第 n 个节点，并且返回链表的每日头结点。

示例：

给定一个链表: 1->2->3->4->5,删除 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 

说明：

给定的链表 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗?倒数第N点

解法：快慢指针

解题思路： 需要删除链表中的倒数第 n 个节点，我们需要知道的个结就是倒数第 n+1 个节点，然后删除删除倒数第 n+1 节点的每日后继节点即可

步骤：

使用 2 个指针：

fast 快指针提前走 n+1 步 slow 指针指向当前距离 fast 倒数第 n 个节点，源码库 初始为 head

然后，删除 fast 、链表 slow 同步向前走，倒数第N点直到 fast.next 为 null

此时，个结fast 为最后一个节点，slow 就是倒数第 n+1 个节点，此时问题就变更为删除链表中的 slow 的后继节点

但存在一个问题，当链表长度为 n 时，fast 是前进不到 n+1 个节点位置的，所以此时有两种解决思路：

创建一个头节点 preHead ，设置 preHead.next = head ，这样就可以解决以上问题，删除倒数第 n 个节点后，返回的服务器托管 preHead.next 即可 另外一种是，fast 快指针提前走 n 步后，判断 fast.next 是否为 null ，即 fast 是否是最后一个节点，如果是，则 head 为倒数第 n 个节点，此时问题可以简化为删除头节点;如果不是， fast = fast.next ，fast 再前进一步，slow 为倒数第 n+1 个节点，也解决了以上问题。

解决方案一：添加 preHead 节点

const removeNthFromEnd = function(head, n) {      let preHead = new ListNode(0)     preHead.next = head     let fast = preHead, slow = preHead     // 快先走 n+1 步     while(n--) {          fast = fast.next     }     // fast、slow 一起前进     while(fast && fast.next) {          fast = fast.next         slow = slow.next     }     slow.next = slow.next.next     return preHead.next }; 

解决方案二：单独处理倒数第 n 节点

const removeNthFromEnd = function(head, n) {      let fast = head, slow = head     // 快先走 n 步     while(--n) {          fast = fast.next     }     if(!fast.next) return head.next     fast = fast.next     // fast、云服务器提供商slow 一起前进     while(fast && fast.next) {          fast = fast.next         slow = slow.next     }     slow.next = slow.next.next     return head }; 

时间复杂度：O(n)

空间复杂度：O(1)

来源：https://github.com/sisterAn/JavaScript-Algorithms

很赞哦!（49579）