网站用的字体,营销型网站的特征,区域教育联盟网站建设,天气预报权威发布题目描述
删除链表的倒数第 N 个结点
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2
输出#xff1a;[1,2,3,5]示例 2#xff1a; 输入#xff1a;head [1], n 1…题目描述
删除链表的倒数第 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 **进阶**你能尝试使用一趟扫描实现吗
解法
解法1
思路先计算链表长度再遍历到第 L−n1 个节点删除节点
java代码
class Solution {public ListNode removeNthFromEnd2(ListNode head, int n) {// 哑节点ListNode dummy new ListNode(0, head);// 链表长度int length ListNode.getLength(head);// 当前节点ListNode cur dummy;// 遍历到第 L−n1 个节点for (int i 1; i length - n 1; i) {cur cur.next;}// 删除节点cur.next cur.next.next;// 返回哑节点的下一个节点即头节点return dummy.next;}
}时间复杂度O(L)其中 L是链表的长度。空间复杂度O(1)。
解法2
双指针
两个指针 first 和 second 同时对链表进行遍历并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时second 就恰好处于倒数第 n 个节点。如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点。
java代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 哑节点ListNode dummy new ListNode(0, head);ListNode first head;ListNode second dummy;// 先让first向后走n步for (int i 0; i n; i) {first first.next;}// 两个同时向后走直到first为nullwhile (first ! null) {first first.next;second second.next;}// 注意此时second是要删除节点的前一个几点second.next second.next.next;// 返回头节点return dummy.next;}
}复杂度
时间复杂度O(L)其中 L是链表的长度。空间复杂度O(1)。
