LeetCode 19. Delete the penultimate node of the linked list

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

Example 1：

 Input ：head = [1,2,3,4,5], n = 2
 Output ：[1,2,3,5]

Example 2：

 Input ：head = [1], n = 1
 Output ：[]

Example 3：

 Input ：head = [1,2], n = 1
 Output ：[1]

Thinking analysis ：

Classic application of pointer , If you want to delete the penultimate n Nodes , Give Way fast Move n Step , And then let fast and slow Move at the same time , until fast Point to the end of the list . Delete slow The node you point to is OK .

First of all, I recommend you to use virtual head node , This facilitates the logic of deleting the actual header node .

1. Definition fast Pointers and slow The pointer , The initial value is virtual head node , Pictured ：
   

2. fast First of all, let's go n + 1 Step , Why n+1 Well , Because that's the only way to move at the same time slow To point to the previous node of the deleted node （ Easy to delete ）, Pictured ：
   

3. fast and slow Move at the same time , until fast Point to the end , Pictured ：
   

4. Delete slow Point to the next node , Pictured ：
   

Code implementation mode 1 ：

public static ListNode removeNthFromEnd(ListNode head, int n) {
    
        //  Create a virtual header node 
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        
        //  Define speed pointer 
        ListNode fast = dummyNode, slow = dummyNode;
        
        // fast Go ahead  n+1  Step , such slow Point to the previous node of the node to be deleted 
        while (n >= 0){
    
            fast = fast.next;
            n--;
        }
			// fast,slow Simultaneous backward transfer 
        while (fast != null){
    
            slow = slow.next;
            fast = fast.next;
        }
        
        slow.next = slow.next.next;

        return dummyNode.next;
    }

Code implementation mode 2 ：

 public ListNode removeNthFromEnd(ListNode head, int n) {
    
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n > 0) {
    
            fast = fast.next;
            n--;
        }
        //  Node to be deleted slow  Last node of 
        ListNode prev = null;
        while (fast != null) {
    
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        //  Of the previous node next Pointer bypass   Node to be deleted slow  Direct to slow The next node of 
        prev.next = slow.next;
      
        return dummy.next;
    }