题目描述

给你一个链表，删除链表的倒数第 n n n 个结点，并且返回链表的头结点。

算法分析：

• 一、 创建虚拟节点dummy，dummy指向head.next
• 二、 指针p1是快指针，p2是慢指针，首先让俩指针都指向第一个节点，p1指针先走n步，然后俩指针一起走，直到p1指针走到头，这时候p2指针就到了第L-n的位置了，也就是我们要删除位置的前一个位置
• 三、 然后让当前位置的next指针指向下下个位置

代码：

/**
 * 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) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p1 = dummy;
        ListNode p2 = dummy;
        for(int i = 0; i < n; i ++) p1 = p1.next;

        while(p1.next != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next = p2.next.next;
        return dummy.next;
    }
}