题目描述
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗
ListNode 数据结构
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
解决方法
如何一趟遍历获取倒数第 n 个节点？使用 2 个指针 first,second，first 在前，second 在后，保持间隔 n 走到链尾，这样 second 就是倒数第 n 个节点
如何删除当前节点操作？前一个节点.next = 前一个节点.next.next
由于头节点没有前一个节点了，如何删除头节点？在头节点前面加入临时头节点，这样原头节点就和普通节点一致
解决了上述 3 个问题可得出以下代码
public ListNode removeNthFromEnd(ListNode head, int n) {
// 为了方便操作建立临时头节点
ListNode tempHead = new ListNode(0);
tempHead.next = head;
ListNode first = tempHead;
ListNode second = tempHead;
// 让 first 先走 n + 1 步
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// 两个指针一起走，当 first 走到链尾，second 就走到倒数第 n + 1 个节点
while (first != null) {
first = first.next;
second = second.next;
}
// 删除下一个节点即删除倒数第 n 个节点
second.next = second.next.next;
return tempHead.next;
}
本文首发：https://lierabbit.cn/2018/08/…