19、删除链表的倒数第N个节点（链表）

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

public class ShanchulianbiaodedaoshudiNgejiedian {
    public ListNode removeNthfromEnd(ListNode head,int n){
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode left = dummy;
        ListNode right = dummy;
        //让快指针先走n步，然后再让快慢指针一起走，
        //直到快指针走到空，此时慢指针指向的就是倒数第n个节点（但是这样不方便做删除操作）
        //删除操作需要找到被删除对象的前一个节点，因此快指针可以先走n+1步，那么慢指针到时候指向的节点就是倒数n+1个节点了
        for (int i = 0; i <=n ; i++) {
            if(right.next!=null) {
                right = right.next;
            }
        }
        //寻找了倒数第n+1个节点
        while (right!=null){
            left = left.next;
            right = right.next;
        }
        //删除倒数第n个节点
        left.next = left.next.next;
        return dummy.next;
    }

    //打印输出
    static void print(ListNode listNode){
        //创建链表节点
        while (listNode!=null){
            if(listNode.next==null){
                System.out.print(listNode.val);
            }else {
                System.out.print(listNode.val + "->");
            }
            listNode = listNode.next;
        }
    }
    public static void main(String[] args) {
        //创建首节点
        ListNode node = new ListNode(1);
        //定义移动节点
        ListNode nextnode = node;

        for (int i = 2; i <=6 ; i++) {
            //生成新节点
            ListNode nodex = new ListNode(i);
            //移动节点指向新节点(连接新节点
            nextnode.next = nodex;
            //把当前节点往后移动
            nextnode = nextnode.next;
        }
        //链表生成完毕
        //直接从首节点打印
        print(node);
        System.out.println();
        ShanchulianbiaodedaoshudiNgejiedian shanchulianbiaodedaoshudiNgejiedian = new ShanchulianbiaodedaoshudiNgejiedian();
        ListNode res = shanchulianbiaodedaoshudiNgejiedian.removeNthfromEnd(node,3);
        print(res);
    }
}

输出结果：

1->2->3->4->5->6
1->2->3->5->6

时间复杂度：O（n）

空间复杂度：O（1）