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

删除的前提是，确定节点位置。

1. 找到倒数第n个节点
1. 采用双指针的方式
2. 快指针先前进n个节点，然后慢指针从头开始，二者并行，直至快指针到达链表尾部
3. 此时，慢指针指向的，就是倒数第n个节点
2. 删除倒数第n个节点
1. 确定倒数第n+1个节点，即待删除节点node的前驱节点pre
2. 设置pre.next = node.next，即前驱节点的next更新为待删除节点的next

综合以上，需要三个指针，一个快指针，一个待删除节点指针，一个前驱节点指针。同时，为了统一删除步骤，减少对特殊情况的排除(如，待删除节点是当前头节点)，这里预先设置一个虚拟头节点preHead，使前驱节点指向preHead。

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

        if (head == null) {
            return head;
        }
        if (head.next == null && n == 1) {
            return null;
        }

        ListNode preHead = new ListNode(0);
        preHead.next = head;
        ListNode fast = head, node = head, pre = preHead;
        
        // 到正序第n个
        while (--n > 0) {
            fast = fast.next;
        }
        // System.out.println(fast.val);

        while (fast != null) {
            if (fast.next == null) {
                pre.next = node.next;
                // fast = fast.next;
                break;
            } else {
                fast = fast.next;
                pre = node;
                node = node.next;
            }
            
        }
        return preHead.next;
    }
}