19. Delete the penultimate node of the linked list (linked list)

subject ： I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list .

Advanced ： Can you try a scan implementation ？

public class ShanchulianbiaodedaoshudiNgejiedian {
    public ListNode removeNthfromEnd(ListNode head,int n){
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode left = dummy;
        ListNode right = dummy;
        // Let the quick pointer go first n Step , Then let the fast and slow pointers go together ,
        // Until the pointer goes to empty , At this time, the slow pointer points to the penultimate n Nodes （ But it's not convenient to delete ）
        // The deletion operation needs to find the previous node of the deleted object , So the fast pointer can go first n+1 Step , Then the node pointed by the slow pointer is the countdown n+1 There are nodes 
        for (int i = 0; i <=n ; i++) {
            if(right.next!=null) {
                right = right.next;
            }
        }
        // Looking for the penultimate n+1 Nodes 
        while (right!=null){
            left = left.next;
            right = right.next;
        }
        // Delete the last n Nodes 
        left.next = left.next.next;
        return dummy.next;
    }

    // Printout 
    static void print(ListNode listNode){
        // Create a linked list node 
        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) {
        // Create the first node 
        ListNode node = new ListNode(1);
        // Define mobile nodes 
        ListNode nextnode = node;

        for (int i = 2; i <=6 ; i++) {
            // Generate new nodes 
            ListNode nodex = new ListNode(i);
            // The mobile node points to the new node ( Connect the new node 
            nextnode.next = nodex;
            // Move the current node back 
            nextnode = nextnode.next;
        }
        // Linked list generation completed 
        // Print directly from the first node 
        print(node);
        System.out.println();
        ShanchulianbiaodedaoshudiNgejiedian shanchulianbiaodedaoshudiNgejiedian = new ShanchulianbiaodedaoshudiNgejiedian();
        ListNode res = shanchulianbiaodedaoshudiNgejiedian.removeNthfromEnd(node,3);
        print(res);
    }
}

Output results ：

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

Time complexity ：O（n）

Spatial complexity ：O（1）