删除链表的倒数第N个结点
题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-100-liked
我的解答：
//方法一：遍历两遍 //时间复杂度：O(L) //空间复杂度：O(1) //注意边界条件：当删除的是链表头节点时，直接返回头节点的下一个节点。 public ListNode removeNthFromEnd(ListNode head, int n) { int count=0; ListNode cur=head; while(cur!=null){ count++; cur=cur.next; } if(count==n){ return head.next; } int pre=count-n; cur=head; while(pre>1){ pre--; cur=cur.next; } cur.next=cur.next.next; return head; } //方法二：哈希表 //时间复杂度：O(L) //空间复杂度：O(L) //用哈希表存储序号和节点，根据序号获取前置节点和需删除的目标节点。 //注意边界条件：当删除的是链表头节点时，直接返回头节点的下一个节点。 public ListNode removeNthFromEnd(ListNode head, int n) { int count=0; ListNode cur=head; Map<Integer,ListNode> map = new HashMap<>(); while(cur!=null){ count++; map.put(count,cur); cur=cur.next; } if(count==n){ return head.next; } ListNode before=map.get(count-n); ListNode target=map.get(count-n+1); before.next=target.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 cur=dummy; for(int i=1; i<length-n+1; i++){ cur=cur.next; } cur.next=cur.next.next; return dummy.next; } public int getLength(ListNode head){ int length=0; ListNode cur=head; while(cur!=null){ length++; cur=cur.next; } return length; } //方法二：栈 //时间复杂度：O(L) //空间复杂度：O(L) public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1,head); Deque<ListNode> stack = new LinkedList<>(); ListNode cur = dummy; while(cur!=null){ stack.push(cur); cur=cur.next; } for(int i=0; i<n; i++){ stack.poll(); } stack.peek().next=stack.peek().next.next; return dummy.next; } //方法三：双指针 //时间复杂度：O(L) //空间复杂度：O(1) public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1,head); ListNode first=head, second=dummy; for(int i=0; i<n; i++){ first=first.next; } while(first!=null){ first=first.next; second=second.next; } second.next=second.next.next; return dummy.next; }分析：
1、方法一采用计算链表长度。在链表头部添加一个哑节点（哨兵节点），避免删除头节点时不存在前置节点的情况，根据链表个数可以很轻松的找到需删除的目标节点的前置节点，从而实现目标节点的删除。此方法与我方法一的解答思路大体一致，只不过我是将边界情况单独考虑了的。
2、方法二采用栈。先遍历一遍链表，将所有节点放入链表，根据栈的后进先出规则，从栈顶弹出n个节点，最后弹出的节点就是需删除的节点，此时栈顶的节点就是前置节点。
3、方法三采用双指针。先将两个双指针隔开n+1个距离，然后两个指针一起向后移动，直到第一个指针指向null，那么第二个指针指向的就是前置节点。
总结
- 本题主要需要思考如何找到需删除节点的前置节点。一共有三种方法，分别为计算链表长度后根据个数去找、将所有节点放入栈后弹出n个节点、将两个指针隔开n+1的距离后一起移动。
- 注意，在链表头节点之前添加一个哑节点（哨兵节点），可以有效的避免出现某些边界情况。
