image.png

思路 双指针 时间复杂度O(n) 空间复杂度O1

1. 首先还是先设置虚拟头节点, 方便处理删除头节点的情况dummyHead.next = head

2. 设置fast = dummyHead, slow = dummyHead;

3. 让fast先走N步, slow再开始走. 当fast指向null 时.说明走到了最后,此时slow的位置就是倒数第N个节点的位置

4. 要删除倒数第N个节点, 我们必须拿到N前面那个节点 就是N -1 ,所以我们让fast走n+1步,当fast走到最后时, slow指向的位置就是倒数第N-1个节点.

5. 此时我们要操作slow.next = slow.next.next即可删除倒数第N个节点

6. 看到一个网友评论的可优化的地方 第二层while循环有个优化点, 当fast.next != null 时候. fast不用走n + 1步
   我个人觉得走n+1步好理解一点. 这个优化点刚开始我都没看明白为啥😄

    public ListNode removeNthFromEnd(ListNode head, int n) {
         ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;
        n++;
        while (n-- > 0 && fast != null) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummyHead.next;
    }
// 优化版
    public ListNode removeNthFromEnd(ListNode head, int n) {
         ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;

        while (n-- > 0 && fast != null) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummyHead.next;
    }