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

1. 题目描述

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

示例：

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

说明：给定的 n 保证是有效的。

进阶：你能尝试使用一趟扫描实现吗？

2. 解题思路

本题中，可以使用比较暴力的方法，遍历两遍链表，第一遍计算出链表的长度，第二遍删除倒数第N个元素，但是这样势必会使得执行效率很低，我们需要考虑只遍历一遍的方法。

如果只遍历一遍，那么我们就需要用上双指针来解决这个问题。这里我们使用快慢指针：

• 先设置快和慢两个指针，开始的时候都指向虚拟的头结点
• 让快指针先走，走到第N个节点
• 然后两个指针一起走，直到快指针指导最后一个节点
• 这时，慢指针指向的节点就是链表的倒数第N个节点
• 删除对应节点即可

最重要的是，快指针和慢指针一直保持相隔N个节点，这样就容易后面的操作。

3. 代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
   // 设置虚拟头结点
   const dummy = new ListNode()
   dummy.next = head
   // 设置快慢指针
   let fast = dummy
   let slow = dummy
   // 快指针先走到第N个节点
   while (n!==0){
       fast = fast.next
       n--
   }
   // 快慢指针一起走，直到快指针指向最后一个节点
   while (fast.next){
       fast = fast.next
       slow = slow.next
   }
   // 删除倒数第N个节点
   slow.next = slow.next.next
   return dummy.next
};

4. 提交结果