Java 19. 删除链表的倒数第 N 个结点_19. 删除链表的倒数第 n 个结点 java

题目要求是一趟扫描

也就是说只遍历一次链表

显然易见这道题遍历两次很快就可以做出来

一遍把链表翻转，一遍找出第n个结点就OK

但只遍历一遍的话，平时习惯了用最简单方法的我，有些为难

但后面还是想出了办法，声明两个节点p,q

q的指针先移动n位(这个n就是题目要求的第n个结点)

这样的话p,q的位置就永远相差n。

当q遍历到最后一个时

p节点就是我们所求的第n个节点，这样一遍扫描就可以完成，不需要两次

要注意特殊链表的处理（比如 [1] )

下面是题目实现

    public static ListNode removeNthFromEnd(ListNode head, int n){
        ListNode p = head;
        ListNode q = head;
        for (int i = 0;i<n;i++){
            q = q.next;
        }
        if (q == null) return head.next;
        while (q.next!=null){
            q = q.next;
            p= p.next;
        }
        p.next = p.next.next;
        return head;
    }