给你一个链表，删除链表的倒数第 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个节点是正数第几个节点。那么就必须得一直获取next，直到无法得到next，那么就到了链表的最后。此时把链表的值都存储在一个列表里面，把对应位置的值去除掉，然后构建链表就行。

代码

var removeNthFromEnd = function(head, n) {
    //把表头的值放入数组中
    let list = [head.val]

    //一边遍历至链表尾部，一边将值添加到数组中
    while (head.next) {
        list.unshift(head.next.val)
        head = head.next
    }

    //删除指定位置的元素
    list.splice(n - 1, 1)
    //如果列表为空，说明只有原链表只有一个节点
    if (list.length === 0) return null

    //构造链表
    return list.reduce((prev, curr) => {
         prev = new ListNode(curr, prev)
         return prev
    }, undefined)
};

优化解题

上面的解题方法可行，但是进行了两次遍历，且最后将整个链表进行了重建，从时间和空间都有一定程度的浪费。更好的方法是如何直接在原链表上将对应的节点删除，删除就是将targetPrev.next = targetPrev.next.next，即将目标节点上一个节点的next设置为next.next，这样就把目标节点从链表中删除了。那么如何只用单循环就得到targetPrev呢？我们仅需要设置两个节点指针start和end，让它们相距n距离，这样当end节点到达最后的时候，start节点就是targetPrev。

代码

var removeNthFromEnd = function(head, n) {
     //设置两个节点指针
     let start = head 
     let end = head

     //让两个节点指针相距n
     for (let i = 0; i < n; i++) {
        end = end.next
     }

     //如果end为空，说明删除的是链表头节点
     if (end === null) {
        return head.next
     }

     //循环，直到end节点到链表最后的节点，此时start节点就是targetPrev节点
     while (end.next) {
        start = start.next
        end = end.next
     }

     //将目标节点的上一个节点的next设置为目标节点的next
     start.next = start.next.next
     return head
};