删除链表的倒数第 N 个结点 | LeetCode-19 | 双指针 | 递归 | 栈 | 四种方法

🙋大家好！我是毛毛张!
🌈个人首页： 神马都会亿点点的毛毛张

这道题还可以用递归法，你想到了吗？毛毛张介绍四种方法

---

LeetCode链接：19. 删除链表的倒数第 N 个结点

---

1.题目描述

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

进阶： 你能尝试使用一趟扫描实现吗？

2.题解

2.1 暴力解法

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 获取链表的长度int length = getLength(head);// 判断要删除的节点位置int index = length - n;// 创建一个虚拟头节点，指向headListNode dummy = new ListNode(0, head);// 要删除的结点的前一个结点ListNode pre = dummy;for (int i = 0; i < index; i++) {pre = pre.next;}// 执行删除操作pre.next = pre.next.next;// 返回新链表的头节点return dummy.next;}// 获取链表长度函数public int getLength(ListNode head) {int length = 0;while (head != null) {length++;head = head.next;}return length;}
}

2.2 双指针- 暴力解法优化

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 创建一个虚拟头节点，指向headListNode dummy = new ListNode(0, head);// 初始化双指针，都指向虚拟头节点ListNode first = dummy, second = dummy;// 让first指针先走n步for (int i = 0; i < n; i++) {first = first.next;}// 同时移动first和second指针，直到first指针到达链表末尾while (first.next != null) {first = first.next;second = second.next;}// 此时second指针的下一个节点就是要删除的节点// 执行删除操作second.next = second.next.next;// 返回新链表的头节点return dummy.next;}
}

2.3 递归

class Solution {int count = 0; // 计数器，用于记录递归层数// 递归法 三步走// 1.确定形参和返回值public ListNode removeNthFromEnd(ListNode head, int n) {// 2.确定单层递归条件if (head == null) return null;// 3.确定单层递归逻辑head.next = removeNthFromEnd(head.next, n); // 递归到链表末尾count++; // 递归返回时增加计数return count == n ? head.next : head; // 如果当前节点是倒数第n个节点，跳过它}
}

2.4 借助栈

• 我们知道递归的本质就是栈，因此我们也可以使用栈来解决这道题目

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//虚设一个头节点  ListNode newHead = new ListNode(0,head);//创建栈用于存储链表结点Stack<ListNode> stack = new Stack<>();//开始迭代，所有结点入栈ListNode cur = newHead;while(cur != null){stack.push(cur);cur = cur.next;}//从栈顶开始弹出元素，一直弹到要删除的位置for(int i=0;i<n;i++){stack.pop();}//再弹出的元素就是要删除的结点的前一个元素ListNode pre = stack.pop();//删除操作pre.next = pre.next.next;//返回结果return newHead.next;}
}

---

都看到这了，不妨一键三连再走吧！

🌈欢迎和毛毛张一起探讨和交流！
联系方式参见个人主页： 神马都会亿点点的毛毛张

---