Delete the penultimate node - linked list topic

First , Solve this problem , Delete the last k Nodes , The first thing that came to mind was the two pointer solution , for example , Delete the penultimate node , We can take a look at the general idea , First, you can define two pointers ,p1 and p2, With first pointer p1 go 2 Step , Then initialize the second pointer p2 Point to head node , Then let the two pointers traverse forward at the same speed at the same time . Since the distance between the two pointers is always kept at 2, When the pointer p1 When pointing to the tail node of the linked list p2 It's just pointing to the bottom of 3 Nodes , Then delete the penultimate node directly .

I started with the normal operation , Caused the array to be out of bounds , Maybe many people will fall into this kind of pit when they just get started with the algorithm .

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution {
    
    /** * * @param head ListNode class  * @param n int integer  * @return ListNode class  */
    public ListNode removeNthFromEnd (ListNode head, int n) {
    
        // write code here
                ListNode pre=head;
                ListNode bre=head;
                for(int i=0;i<n;i++)
        {
    
        pre=pre.next;
        }
        while(pre.next!=null)
        {
    
        pre=pre.next;
        bre=bre.next;
        }
        bre.next=bre.next.next;
        return head;
    }
}

Later, it was found that the use of sentinel nodes can perfectly solve the problem of array out of bounds . You can compare the difference between the two codes . Fine products

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution {
    
    /** * * @param head ListNode class  * @param n int integer  * @return ListNode class  */
    public ListNode removeNthFromEnd (ListNode head, int n) {
    
        // write code here
      ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode front=head,back=dummy;
        for(int i=0;i<n;i++)
        {
    
            front=front.next;
        }
        while(front!=null)
        {
    
            front=front.next;
            back=back.next;
        }
        back.next=back.next.next;
        return dummy.next;
    }
}