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

力扣题目链接(opens new window)

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

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

思路

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

分为如下几步：

• 定义fast指针和slow指针，初始值为虚拟头结点，如图：

• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
• fast和slow同时移动，直到fast指向末尾，如题：
• 删除slow指向的下一个节点，如图：

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    let fakeHead = new ListNode()
    fakeHead.next = head
    let fast = fakeHead
    let slow = fakeHead
    let count = 0
    while (count !== n) {
        fast = fast.next
        count++
    }
    while (fast.next !== null) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return fakeHead.next
};