asp.net+h5网站开发,网站网页设计教程,制作网站软件作品,wordpress产品菜单入口
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试#xff1f;力扣提供海量技术面试资源#xff0c;帮助你高效提升编程技能#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-nth-node-from-end…入口
力扣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]提示 链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz 方法一栈
Java实例
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 创建一个虚拟节点作为头节点以便在删除第一个节点时能够方便地处理ListNode dummy new ListNode(0, head);// 创建一个栈来保存节点用于倒数第n个节点的查找DequeListNode stack new LinkedListListNode();// 创建一个当前节点指针初始化为虚拟节点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;}
}复杂度分析 时间复杂度O(L)L 是链表的长度。 空间复杂度O(1)。
