一、题目描述

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

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

示例1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

二、思路分析

链表不能倒序遍历，所以这道题的难点在于这个“倒数第 N 个”如何定位。
我们可以将“倒数第 N 个” 转变为：“正数第 len - n + 1"个。
我们可以先遍历一遍得到链表长度len，再遍历一遍找到第len - n + 1个结点。

但是有没有办法可以不遍历两遍的呢？ 那就用快慢指针吧：

• 快指针先走n步，
• 快指针、慢指针再一起往前走
• 当快指针走到最后一个结点时，两个指针都停下来
• 这时慢指针所指的位置，就是倒数第 n 个结点的前一个结点

此时就方便我们进行删除了：

slow.next = slow.next.next

三、AC 代码

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
const removeNthFromEnd = function(head, n) {
    // 初始化 dummy 结点
    const dummy = new ListNode()
    // dummy指向头结点
    dummy.next = head
    // 初始化快慢指针，均指向dummy
    let fast = dummy
    let slow = dummy

    // 快指针闷头走 n 步
    while(n!==0){
        fast = fast.next
        n--
    }
    
    // 快慢指针一起走
    while(fast.next){
        fast = fast.next
        slow = slow.next
    }
    
    // 慢指针删除自己的后继结点
    slow.next = slow.next.next
    // 返回头结点
    return dummy.next
};

四、总结

• 利用快慢指针可以更好的以空间换时间
• “倒数第 N 个” 可以转变为：“正数第 len - n + 1"个。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情