题解 | #删除链表的倒数第n个节点# 双指针法

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 思路：因为需要用双指针记录头结点，这里考虑到删除第一个元素不好删除，所以新建一个节点指向头结点
     *		设置两个指针,记录新节点，可以让p2先走n + 1步（为啥是n + 1，因为引入了一个新的节点），再让p1和p2	 *		同时走，当p2走到链表尾部的时候，p1，就是链表倒数第n + 1个节点，如果要删除倒数第n个，
	 *  	直接让p1的下一个指向p1的下一个的下一个
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode s = new ListNode(-1);
        s.next = head;
        ListNode p1 = s;
        ListNode p2 = s;

        int c = 0;
	  	while(c < n + 1){
		  p2 = p2.next;
		  c++;
		}
        while(p2 != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return s.next;
       }
}