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

文章目录

- 题目
- 方法一：节点加入集合找索引
- 方法二：直接计算长度,然后找出要删除的节点的前一个节点
- 方法三：栈
- 方法四：前后双指针

题目

这题的关键在与两个点

一定要设置一个哑结点，防止删除第一个元素时，导致空指针异常
删除链表的元素其实就等价于找到这个元素的前一个元素

在这里插入图片描述

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

在这里插入图片描述

先将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<>();
            //将链表节点存到list
            ListNode 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 + 1
               int 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;

        }