o2o网站建设市场,wordpress标签伪静态态,wordpress v2ex,青岛谷歌优化公司大家好#xff01;我是曾续缘#x1f916; 今天是《LeetCode 热题 100》系列 发车第 29 天 链表第 8 题 ❤️点赞 #x1f44d; 收藏 ⭐再看#xff0c;养成习惯 删除链表的倒数第 N 个结点 给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头… 大家好我是曾续缘 今天是《LeetCode 热题 100》系列 发车第 29 天 链表第 8 题 ❤️点赞 收藏 ⭐再看养成习惯 删除链表的倒数第 N 个结点 给你一个链表删除链表的倒数第 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 进阶你能尝试使用一趟扫描实现吗 难度 解题方法
这道题目是要求删除链表的倒数第 N 个节点并返回删除节点后的链表头结点。我们可以使用一趟扫描实现。
首先我们需要定义一个哑结点(dummy node)即在头结点之前加一个虚拟的节点hair这样方便处理删除头结点的情况。
然后我们定义一个递归函数 recurse用于递归地找到链表的末尾并返回当前节点的位置。
在递归函数中我们通过递归到链表末尾并返回时使用一个全局变量 n 记录当前是倒数第几个节点。当 n 等于 0 时表示当前节点的下一个节点就是要删除的节点此时我们将当前节点的 next 指针指向下下个节点即完成了删除操作。
最后在 removeNthFromEnd 函数中我们调用递归函数 recurse并返回哑结点的下一个节点作为新的链表头结点。
这种方法的关键在于使用递归返回和局外变量 n 记录返回次数来找到要删除的节点的位置并且只需遍历一次链表即可完成删除操作。同时通过使用哑结点能够更方便地处理删除头结点的情况。
Code
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {private int n;private void recurse(ListNode cur){if(cur null){return;}recurse(cur.next);if(n 0){cur.next cur.next.next;}n--;}public ListNode removeNthFromEnd(ListNode head, int n) {this.n n;ListNode hair new ListNode(0, head);recurse(hair);return hair.next;}
}
