做外卖有哪些网站,长春seo顾问,wordpress类与函数的差别,互联网营销公司排行榜题目链接#xff1a;https://leetcode.cn/problems/remove-nth-node-from-end-of-list/进阶#xff1a;你能尝试使用一趟扫描实现吗#xff1f;解题思路#xff1a;最简单的方法是先遍历一次链表#xff0c;得到链表的长度len#xff0c;然后再一次遍历链表#xff0c;遍…题目链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/进阶你能尝试使用一趟扫描实现吗解题思路最简单的方法是先遍历一次链表得到链表的长度len然后再一次遍历链表遍历到第len-n个节点时就是要删除节点的前驱tem:如果len-n0,说明要删除的节点是第一个节点直接return head.next否则tem.nexttem.next.next然后reutrn head。但是上面这种方式需要两趟扫描下面有两种方式可以使用一趟扫描实现以空间换时间从前往后遍历一次链表将每次遍历的节点保存在数组list中。遍历完成之后就可以得到数组的长度size那么第index size-n-1个节点就是要删除节点的前驱如果index0说明要删除第一个节点直接return head.next否则list[index].nextlist[index].next.next然后 return headAC代码class Solution {public static ListNode removeNthFromEnd(ListNode head, int n) {ArrayListListNode list new ArrayList();ListNode ans head;while (ans ! null) {list.add(ans);ans ans.next;}int size list.size();int removeIndexBefore size - n - 1;if (removeIndexBefore 0) {return head.next;}ListNode removeIndexBeforeNode list.get(removeIndexBefore);removeIndexBeforeNode.next removeIndexBeforeNode.next.next;return head;}
}快慢双指针法使用两个指针一个先走一个后走让第一个指针first先走n步如果firstnull说明要删除的节点是第一个节点直接return head.next然后第一个指针first和第二个指针second同时走当first走到最后一个节点时(此时fist.nextnull)那么第二个指针的位置就是要删除节点的前驱,令second.nextsecond.next.next然后return headAC代码class Solution {public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode first head;ListNode second head;for (int i 0; i n; i) {first first.next;}if (first null) {return head.next;}while (first.next ! null) {first first.next;second second.next;}second.nextsecond.next.next;return head;}
}
