【LeetCode-中等题】19. 删除链表的倒数第 N 个结点

题目

这题的关键在与两个点

1. 一定要设置一个哑结点，防止删除第一个元素时，导致空指针异常
   

2. 删除链表的元素其实就等价于找到这个元素的前一个元素
   

方法一：节点加入集合找索引

先将ListNode存到list 然后直接找到要删除节点的前一个节点即可（node.next = node.next.next）

  public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode pre = new ListNode(0, head);//创建哑结点  解决要删除的元素时第一个 空指针异常List<ListNode> list = new ArrayList<>();//将链表节点存到listListNode h = pre;while(h != null){list.add(h);h = h.next;}//找到要删除的数的前一个节点ListNode node = list.get(list.size()-1-(n-1)-1);node.next = node.next.next;return pre.next;}

方法二：直接计算长度,然后找出要删除的节点的前一个节点

       public static ListNode removeNthFromEnd(ListNode head, int n) {//得出链表的长度int length   =  getLength(head);ListNode pre = new ListNode(0, head);//创建哑结点  解决要删除的元素时第一个 空指针异常//倒数n个 为  length - n + 1int l = length - n + 1;ListNode cur = pre;for (int i = 1; i < l ; i++ ) {cur = cur.next;}cur.next = cur.next.next;return pre.next;}//计算链表长度public static int getLength(ListNode head){int len = 0;while(head !=null){len ++;head = head.next;}return len;}

方法三：栈

依次入栈，直到null 然后要删除的元素 n = 多少 就弹出对少元素 弹出的元素就是要删除的元素 例如找n=1 倒数第一个 则直接弹出栈顶元素删除即可

此时当弹出n个数之后 ，此时栈顶其实就是要删除的数的前一个数了，也满足将删除链表元素转换为找到要删除元素的前一个元素

   public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);//哑结点  删除第一个元素空指针异常Deque<ListNode> stack = new LinkedList<ListNode>(); //栈ListNode cur = dummy;while (cur != null) {stack.push(cur);cur = cur.next;}for(int i = 0; i<n ; i++){stack.pop();//弹出对应的栈顶元素  最后弹出的元素就是要删除的元素}//此时要删除的前一个元素时栈顶元素ListNode pre = stack.peek();pre.next = pre.next.next;return dummy.next;}

方法四：前后双指针

关键在于指针的设置，fast起始就比slow快一个节点，然后按照n=？ fast往前移动？个位置，然后再slow和fast同步移动，直到fast走到null，此时slow指向的就是要删除元素的前一个位置（也就是为什么开始就要fast比slow快一个位置的原因，不然等fast走到null了，结果slow指向的要删除的元素，这样不太好执行node.next = node.next.next操作，因为删除链表的元素其实就等价于找到这个元素的前一个元素）

    public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);//哑结点  防止删除第一个元素空指针异常ListNode  fir = head;ListNode  bef = dummy;//先指针领先 bef  n 个位置for(int i=0;i<n;i++){fir = fir.next;}//当 fir遍历到链表的末尾时， bef的下一个节点就是我们需要删除的节点。while(fir !=null){fir =fir.next;bef = bef.next;}bef.next = bef.next.next;return dummy.next;}