leetcode 19. Delete the penultimate node of the linked list

difficulty ： secondary
The frequency of ：75
problem ： I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list

** Their thinking ：** Double pointer , Just navigate to the node to be deleted and the previous node , You can delete
Be careful ：

• Last but not least n Nodes , You can use a tail Pointer first n Step
• then tail and cur Went together , until tail Get to the last step
• This is the time cur Is the node to be deleted
• pre To locate the node before the node to be deleted
• Because there may only be one node , It will be empty after deletion , This situation needs to be written out in advance

Code ：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
    
        // The first node has active , So you need a virtual head node 
        ListNode dummyhead=new ListNode(0);
        dummyhead.next=head;
        // Double pointer , Fixed distance pointer moves together 
        ListNode tail=head,pre=dummyhead,cur=head;
        // When there is only one node , Delete must be for null
        if(head.next==null) return null;
        // Last but not least n individual , Last but not least n Moved to the last one n-1 individual 
        for(int i=0;i<n-1;i++){
    
            tail=tail.next;
        }
        // The two pointers move together , When tail When you reach the last node , The location you just reached is the node you want to delete 
        while(tail.next!=null){
    
            //pre Is used to mark the previous node of the deleted node 
            pre=cur;
            cur=cur.next;
            tail=tail.next;
        }
        // Delete cur node 
        pre.next=cur.next;
        return dummyhead.next;
    }
}