[每日算法 - 阿里机试] leetcode19. 删除链表的倒数第 N 个结点

本文主要是介绍[每日算法 - 阿里机试] leetcode19. 删除链表的倒数第 N 个结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

入口

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

题目描述

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

方法一：栈

Java实例

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 创建一个虚拟节点作为头节点，以便在删除第一个节点时能够方便地处理ListNode dummy = new ListNode(0, head);// 创建一个栈来保存节点，用于倒数第n个节点的查找Deque<ListNode> stack = new LinkedList<ListNode>();// 创建一个当前节点指针，初始化为虚拟节点ListNode cur = dummy;// 将链表中的每个节点推入栈中while (cur != null) {stack.push(cur);cur = cur.next;}// 弹出栈中的前n个节点，使栈顶元素为倒数第n个节点的前一个节点for (int i = 0; i < n; ++i) {stack.pop();}// 获取倒数第n个节点的前一个节点ListNode prev = stack.peek();// 将前一个节点的next指针跳过倒数第n个节点，直接指向倒数第n个节点的下一个节点prev.next = prev.next.next;// 获取新链表的头节点（去除了虚拟节点）ListNode ans = dummy.next;// 返回新链表的头节点return ans;}
}

复杂度分析

时间复杂度：O(L)， L 是链表的长度。
空间复杂度：O(L)， L 是链表的长度，主要为栈的开销。

方法二：双指针

使用快慢指针的方式，快指针与慢指针相差n-1，即快指针比慢指针超前了 n 个节点。两个指针同时遍历链表，当快指针指向null时，此时慢指针正好指向倒数第n个元素。

Java示例

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 创建一个虚拟节点，用于处理删除第一个节点的情况ListNode dummy = new ListNode(0, head);// 创建两个指针，一个指向链表的头节点，另一个指向虚拟节点ListNode first = head;ListNode second = dummy;// 将第一个指针向前移动n个节点for (int i = 0; i < n; ++i) {first = first.next;}// 同时移动第一个和第二个指针，直到第一个指针到达链表末尾while (first != null) {first = first.next;second = second.next;}// 此时第二个指针指向倒数第n个节点的前一个节点// 将前一个节点的next指针跳过倒数第n个节点，直接指向倒数第n个节点的下一个节点second.next = second.next.next;// 获取新链表的头节点（去除了虚拟节点）ListNode ans = dummy.next;// 返回新链表的头节点return ans;}
}