题目描述
给你一个链表，删除链表的倒数第 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
题目评估
知识点：链表、双指针
官方难度：中等
分析
先遍历一遍得到长度，然后长度减n加1得到正序下要删除的节点位置，再遍历删除，总共遍历两遍。
进阶版：
定义两个指针，使第一个指针指向第二个指针前n个节点，当第一个指针走到尾时，第二个指针所指向的节点恰好是倒数第n个节点。
Java代码题解
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode current = head;
// 计算链表的节点数量
int count = 0;
while (current != null) {
count++;
current = current.next;
}
// 要删除的正序
int rn = count - n + 1;
current = head;
// 如果删除第一个节点
if (rn == 1) {
head = current.next;
current = null;
return head;
}
count = 2;
// 指针后移
ListNode prior = current;
current = current.next;
while (current != null) {
if (count == rn) {
// 将前一个节点指向下一个节点
prior.next = current.next;
current = null;
return head;
}
prior = current;
current = current.next;
count++;
}
return head;
}
}
进阶版一次遍历：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 创建一个假头指向真头
ListNode myHead = new ListNode(-1, head);
// 创建双指针的前置
ListNode fPrior = myHead;
ListNode sPrior = myHead;
// 创建双指针
ListNode first = fPrior.next;
ListNode second = sPrior.next;
// 正序计数
int count = 1;
while (first != null) {
// 第一个指针向前移动
fPrior = first;
first = first.next;
// 当第一个指针走到正序第n个节点的时候第二个指针开始移动
if (count > n) {
// 第二个指针向前移动
sPrior = second;
second = second.next;
}
count++;
}
// 此时第二个指针所指向的节点就是倒数第n个节点
// 删除第二个指针的节点
if (sPrior.next == head) {
// 如果第二个指针节点是真头节点做特殊处理
head = head.next;
} else {
sPrior.next = second.next;
}
return head;
}
}
复杂度分析
时间复杂度：O(n)，n为链表的长度
空间复杂度：O(1)