剑指Offer|LCR 021. 删除链表的倒数第 N 个结点

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

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

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

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

法1：遍历

分析：
先遍历计算当前链表的长度size，倒数第n个结点，相当于正数第size-n个结点，只需要找到要删除的前一个结点。

时间复杂度：$O(n)$

空间复杂度：$O(1)$

class ListNode {constructor(val = 0, next = null) {this.val = val;   // 节点的值this.next = next; // 下一个节点}
}var removeNthFromEnd = function(head, n) {// 第一步：计算链表的长度let size = 0;let current = head;while (current !== null) {size++;current = current.next;}// 处理删除的是头节点的情况if (n === size) {return head.next; // 如果要删除的是头结点，直接返回 head.next}// 第二步：找到要删除的前一个节点let prev = head;for (let i = 0; i < size - n - 1; i++) {prev = prev.next;}// 第三步：删除倒数第n个节点prev.next = prev.next.next;// 返回新的头节点return head;
};
function printNode(node){while(node !== null){console.log(node.val)node = node.next}
}
// 创建链表节点
let root = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
printNode(root)
console.log('-----------');
printNode(removeNthFromEnd(root, 2));

法2：虚拟头结点，双指针

分析：

创建一个虚拟头结点，方便处理删除头节点的情况

看例子head = [1,2,3,4,5], n = 2

定义虚拟头结点dummy=new ListNode(0) ,令dummy.next = head;

主要是定义两个指针front和back，先让front先走n-1步，这样front和back之间的间距就是n-1,当front指针遍历到最后一个的时候，back指针恰好是倒数第n+1个指针，要删的那个就在back后面。

时间复杂度：$O(n)$

空间复杂度：$O(1)$

class ListNode {constructor(val = 0, next = null) {this.val = val;this.next = next;}
}var removeNthFromEnd = function(head, n) {// 创建一个虚拟头结点，方便处理删除头节点的情况let dummy = new ListNode(0);dummy.next = head;let front = head, back = dummy;// 先让 front 移动 n 步for (let i = 0; i < n; i++) {front = front.next;}// 当 front 移动到末尾时，//back 就是倒数第 n 个节点的前一个节点while (front !== null) {front = front.next;back = back.next;}// 删除倒数第 n 个节点back.next = back.next.next;// 返回新的头节点return dummy.next;
};// 测试代码
let root = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
console.log(removeNthFromEnd(root, 2)); // 删除倒数第二个节点