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

主要思想：

利用伪头结点使得慢指针p与快指针q相距n+1，先让快指针向前走n步，然后快慢指针一起往后走，知道快指针到达最后一个元素，慢指针所在位置即倒数第n+1的位置，此时直接将慢指针的next指针指向慢指针的next的next即可删除倒数第n个元素。

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        // 伪头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        ListNode q = dummy;
        int step = 0;
        // q向前走n步
        while (step < n) {
            q = q.next;
            step++;
        }
        // q遍历到最后一个node,此时q为前n+1的位置，直接q.next = q.next.next;即可删除倒数第n个节点
        while (q.next != null) {
            q = q.next;
            p = p.next;
        }
        p.next = p.next.next;
        return dummy.next;
    }
}