029删除链表的倒数第N个结点

删除链表的倒数第N个结点题目链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答//方法一遍历两遍 //时间复杂度O(L) //空间复杂度O(1) //注意边界条件当删除的是链表头节点时直接返回头节点的下一个节点。 public ListNode removeNthFromEnd(ListNode head, int n) { int count0; ListNode curhead; while(cur!null){ count; curcur.next; } if(countn){ return head.next; } int precount-n; curhead; while(pre1){ pre--; curcur.next; } cur.nextcur.next.next; return head; } //方法二哈希表 //时间复杂度O(L) //空间复杂度O(L) //用哈希表存储序号和节点根据序号获取前置节点和需删除的目标节点。 //注意边界条件当删除的是链表头节点时直接返回头节点的下一个节点。 public ListNode removeNthFromEnd(ListNode head, int n) { int count0; ListNode curhead; MapInteger,ListNode map new HashMap(); while(cur!null){ count; map.put(count,cur); curcur.next; } if(countn){ return head.next; } ListNode beforemap.get(count-n); ListNode targetmap.get(count-n1); before.nexttarget.next; return head; }分析​ 代码的时间复杂度为O(n)空间复杂度为O(1)。​ 方法一的解题思路先遍历一遍数链表节点的总个数然后再遍历一遍节点找到需删除节点的前一个节点更改此节点的下一个节点为删除节点的下一个节点注意删除节点为链表头节点时此时没有前置节点故直接返回头节点的下一个节点即可。​ 方法二的解题思路遍历链表用哈希表存储序号和节点最后根据序号获得前置节点和需删除的目标节点赋值前置节点的下一个节点为目标节点的下一个节点即可。​ 方法一和方法二都需要注意“删除的是链表头节点”的边界条件。若属于边界条件直接返回头节点的下一个节点。看了官方题解后的解答//方法一计算链表长度 //时间复杂度O(L) //空间复杂度O(1) //关键添加一个哑节点哨兵节点这样就可以不用单独考虑边界情况了 public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(-1,head); int length getLength(head); ListNode curdummy; for(int i1; ilength-n1; i){ curcur.next; } cur.nextcur.next.next; return dummy.next; } public int getLength(ListNode head){ int length0; ListNode curhead; while(cur!null){ length; curcur.next; } return length; } //方法二栈 //时间复杂度O(L) //空间复杂度O(L) public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(-1,head); DequeListNode stack new LinkedList(); ListNode cur dummy; while(cur!null){ stack.push(cur); curcur.next; } for(int i0; in; i){ stack.poll(); } stack.peek().nextstack.peek().next.next; return dummy.next; } //方法三双指针 //时间复杂度O(L) //空间复杂度O(1) public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(-1,head); ListNode firsthead, seconddummy; for(int i0; in; i){ firstfirst.next; } while(first!null){ firstfirst.next; secondsecond.next; } second.nextsecond.next.next; return dummy.next; }分析​ 1、方法一采用计算链表长度。在链表头部添加一个哑节点哨兵节点避免删除头节点时不存在前置节点的情况根据链表个数可以很轻松的找到需删除的目标节点的前置节点从而实现目标节点的删除。此方法与我方法一的解答思路大体一致只不过我是将边界情况单独考虑了的。​ 2、方法二采用栈。先遍历一遍链表将所有节点放入链表根据栈的后进先出规则从栈顶弹出n个节点最后弹出的节点就是需删除的节点此时栈顶的节点就是前置节点。​ 3、方法三采用双指针。先将两个双指针隔开n1个距离然后两个指针一起向后移动直到第一个指针指向null那么第二个指针指向的就是前置节点。总结本题主要需要思考如何找到需删除节点的前置节点。一共有三种方法分别为计算链表长度后根据个数去找、将所有节点放入栈后弹出n个节点、将两个指针隔开n1的距离后一起移动。注意在链表头节点之前添加一个哑节点哨兵节点可以有效的避免出现某些边界情况。