1、题干

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

示例 1：
在这里插入图片描述
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

2、解题

前提给定：（链表节点的定义和链表的形成）

链表节点定义如下：

// 链表节点
public class ListNode {int val;ListNode next;ListNode() {}ListNode(int x) {val = x;}
}

链表构建过程示例：（如上示例1）

public static void main(String[] args) {ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);ListNode node5 = new ListNode(5);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;ListNode node = removeNthFromEnd(node1, 2);while (node != null) {System.out.println(node.val);node = node.next;}}

方法一：（计算链表长度）

通过一个临时节点，指向头结点，依次遍历到尾节点，计算遍历的次数得到链表的长度；
结合链表的长度和倒数的位置，可以得到正序要删除节点的位置。
正向遍历到该位置的前一个元素，进行删除节点。

代码示例：

 public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode preResult = new ListNode();preResult.next = head;ListNode pre = preResult;  // 临时变量，找到要删除的位置，进行删除ListNode tail = head;    // 尾指针，用于遍历到尾部，找到链表的长度// 找到链表长度，计算得到要删除的节点位置。int len = 0;while (tail!=null){len++;tail = tail.next;}int position = len - n;   // 得到正序要删除节点的位置下标// 找到位置，删除元素for (int i = 0; i < position; i++) {pre = pre.next;}ListNode next = pre.next;    // 找到要删除的节点nextpre.next = next.next;   // 断开pre和next的指向关系，使pre指向enxt的后面节点next.next = null;  // next与链表测地断开return preResult.next;}

方法二：（利用栈的先进后出特性）

将所有的节点添加到栈中，那么倒数第N个节点，实际就是栈顶向下的第N节点。
依次出站N个元素，那么此时栈顶元素就是要删除节点的前一个元素。此时回到链表直接删除当前元素的下一个元素即可。

代码示例：

 public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode preResult = new ListNode();preResult.next = head;ListNode pre = preResult;  // 中间变量，依次入栈操作用// 通过pre使链表元素依次入栈Stack<ListNode> stack = new Stack<>();while (pre!=null){stack.push(pre);pre = pre.next;}// 弹出元素，将目标位置元素和后面的元素全部弹出for (int i = 0; i < n; i++) {stack.pop();}// 此时，站顶元素为目标元素的前一个元素if (!stack.isEmpty()){pre = stack.peek();// 删除目标元素pre.next = pre.next.next;} else {return new ListNode();}return preResult.next;}

方法三：（双指针法）

利用两个指针。
第一个还真向前遍历N个元素，第二个指针指向起点。两个指针之间的距离就是N。
之后，两个指针一起向后移动，因为两个指针距离N，当第一个指针达到尾部的时候，那么此时第二个节点刚好就是要删除的节点。
实际为了删除，我们要获取的是目标删除节点的前一个节点。所以第二个指针初始化应该是链表头结点的前驱节点。

代码示例：

 public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);ListNode first = head;ListNode second = dummy;for (int i = 0; i < n; ++i) {first = first.next;}while (first != null) {first = first.next;second = second.next;}second.next = second.next.next;ListNode ans = dummy.next;return ans;}