题目
要求
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
答案
先看看直接思路，首先遍历一遍，计算出元素的个数，之后计算出正向遍历要删除的元素，注意的是要创建一个虚拟节点，目的是可能删除头节点，如果删除头节点，没有虚拟节点，不易删除，当然也可以做特殊情况，比如说判断删除的元素为头节点，直接返回 head.next 也是可以的。
public static ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return head;
}
int size = 0;
ListNode virtual = head;
// 计算元素的个数
while (virtual != null) {
size++;
virtual = virtual.next;
}
// 移除元素，使用虚拟节点，都在如果删除头节点，无法删除
ListNode virtualHead = new ListNode(0);
virtualHead.next = head;
virtual = virtualHead;
// 正向第 n 个元素，索引从 1 开始
int len = size - n + 1;
int index = 1;
// 遍历到删除元素的前一个元素
while (index < len) {
index++;
virtual = virtual.next;
}
// 删除元素
virtual.next = virtual.next.next;
return virtualHead.next;
}
想想还有没有其它思路，链表有递归的属性在，那是不是可以递归解决呢？递归的思路也是也简单，就是在递归到最后开始返回，从 1 开始返回，当返回的数字等于 n 的时候就可以删除了，如下：
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode virtualHead = new ListNode(0);
virtualHead.next = head;
myRemoveNthFromEnd(virtualHead, n);
return virtualHead.next;
}
private static int myRemoveNthFromEnd(ListNode virtualHead, int n) {
if (virtualHead.next == null) {
return 1;
}
int result = myRemoveNthFromEnd(virtualHead.next, n);
// 删除
if (result == n) {
virtualHead.next = virtualHead.next.next;
}
return result + 1;
}