Leetcode P19.
这道题目，需要注意，这里的链表是单向链表。因为没有逆向指针，所谓“倒序第 n 个节点”，便无从说起。我们可以转换思路，倒序第 n 个节点，在一个大小为 sz 的链表中，同时也会是正序第 sz+1-n 个节点。 遍历链表，同时计数 i，直到末尾, i==sz，此过程中可能出现如下情况：
- 遍历部分不够长，第 i+1-n 个节点尚未出现，即 i+1-n <= 0，
- 遍历部分长度达到临界值，第 i+1-n 个节点恰好出现，即首次出现 i+1-n > 0；
- 遍历部分足够长，直到末尾，第 i+1-n 个节点在游标指针的落后位置，也就是更靠近链表 head 的位置，当然此过程中的 i+1-n > 0 依然是成立的。
基于这种思路，考虑使用快慢指针，快指针指向链表尾部，遍历链表，慢指针指向目标节点。在这个题中，因为还要移除目标指针，所以还需要一个额外的指针，指向目标节点的 prev 节点，该指针应滞后一步于慢指针。
各指针移动过程如下：
- 快指针先移动，i 随着快指针的移动渐增，慢指针尚未开始移动；
- 快指针移动，直到临界点，正序第 sz+1-n 个节点出现，此时 i+1-n > 0 ，此时慢指针准备开始移动，指向 head；
- 快慢指针移动，滞后一步于慢指针的 prev 指向旧的慢指针，也开始移动；
- 快、慢、滞后指针分别移动，直到快指针遍历完整个链表，三个指针停止移动；
此时，判断慢指针即为待移除的节点。判断慢指针处于的几种状态即可： 慢指针从未移动（slow==null）、 慢指针恰巧指向第一个节点而滞后指针尚未有指向（slow==head && prev==null）、 慢指针移动到某个未知而之后指针也已开始移动（slow!=null && prev!=null）。
最后根据分析，写出代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = null; // 目标节点
ListNode prev = null;
int i = 1;
while (fast != null) {
fast = fast.next;
i++;
if (i + 1 - n > 0) {
if (slow == null) {
slow = head;
} else {
prev = slow;
slow = slow.next;
}
}
}
if (slow == null) {
return head;
}
if (prev == null) {
return slow.next;
} else {
prev.next = slow.next;
return head;
}
}
}
链表节点结构定义
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
更多精彩内容，欢迎关注我的公众号：逻魔代码