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

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

题目描述

给你一个链表，删除链表的倒数第 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

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list

解题步骤

这个题比较直观，我们先用快指针多走n步(倒数第n个即走n步) 然后快慢指针同步走 直到快指针走到尾结点 那么慢指针就是倒数n+1节点， 让其指向Next.Next即可,

• 还是虚拟节点的小细节，因为头结点可能是需要被移除的， 所以头结点不确定 需要用虚拟节点

代码如下

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    //特判
    if n <= 0 {
        return head
    }

    //建立虚拟头节点
    virtual := &ListNode{
        Next: head,
    }

    fastNode, slowNode := virtual, virtual
    //快指针从虚拟节点开始走n步。期间当step < n && fastNode == nil 表示n非法 直接返回false
    for i:=0; i<n && fastNode != nil; i++{
        fastNode = fastNode.Next
    }
    //非法n
    if fastNode == nil { 
        return head
    }

    //当step == n 并且 fastNode != nil  表示成立
    for fastNode.Next != nil {
        fastNode = fastNode.Next
        slowNode = slowNode.Next
    }

    //慢指针开始从虚拟节点 和 快指针当前位置同步走  直到fastNode.Next == nil 此时slowNode的节点即为倒数n+1
    slowNode.Next = slowNode.Next.Next
    //返回虚拟节点的下一个指向即可
    return virtual.Next
}