日拱算法： 删除链表的倒数第 N 个结点

「这是我参与2022首次更文挑战的第7天，活动详情查看：2022首次更文挑战」

---

日拱算法，功不唐捐。

平常基本上没有用过链表数据结构，链表的优势在于插入的时间复杂度良好 O(1)。

闲言少叙，冲就完事儿！

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

比如：

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

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

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

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

题解：

假如我们定义链表长度为l，则倒数第 n 项，正数第 l-n+1 项，其前一项为第 l-n 项；

• 双指针法解法

让前后指针 forward 和 backward 相差为 n 后同时向后推进，则当 forward 到达终点，即 forward.next 为 null 时，backward 恰好到达倒数第 n 项的前一项，连接倒数第 n 项的前后项；

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(0, head)
    let forward = dummy, backward = dummy
    while (n--) {
        forward = forward.next
    }
    while (forward.next) {
        forward = forward.next
        backward = backward.next
    }
    backward.next = backward.next.next
    return dummy.next
};

提交通过。

除了双指针，还有简单暴力的把链表转换成数组处理：

• 数组法

将链表转换为纯数组，数组内存放链表的值，删除倒数第n个数，再将数组转换为链表；

var removeNthFromEnd = function(head, n) {
    let newArr = []
    let dummy = new ListNode()
    let newList = dummy
    while(head){
        newArr.push(head.val)
        head = head.next
    }
    newArr.splice(newArr.length - n, 1)       
    for(let i = 0; i < newArr.length ;i++){
        newList.next = new ListNode(newArr[i]);
        newList = newList.next;
    }
    return dummy.next
};

拓展：还可以将链表节点依次存入数组stack栈，再将栈的后n个元素弹出，暴露出链表倒数第n个数的前一个节点，将其与倒数第n个数的后一个节点相连：

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(0, head)
    const stack = new Array()
    let pushList = dummy
    while (pushList != null) {
        stack.push(pushList)
        pushList = pushList.next
    }
    for (let i = 0; i < n; i++) {
        stack.pop()
    }
    let peek = stack[stack.length - 1]
    peek.next = peek.next.next
    return dummy.next
};

---

链表的关键在于判断下一节点的指向，链表和数组也可以互相转换，但是显得会有些生硬，双向指针是更灵活的做法。