共计 1543 个字符，预计需要花费 4 分钟才能阅读完成。
原文链接：https://wangwei.one/posts/jav…
前面，我们实现了 两个有序链表的合并 操作，本篇来聊聊，如何删除一个链表的倒数第 N 个节点。
删除单链表倒数第 N 个节点
Leetcode 19. Remove Nth Node From End of List
给定一个单链表，如: 1->2->3->4->5，要求删除倒数第 N 个节点，假设 N = 2，并返回头节点。
则返回结果：1->2->3->5 .
解法一
这一题的难度标记为 medium，解法一比较容易想出来，我个人觉得难度不大。
思路
循环两遍：
先遍历一遍，求得整个链表的长度。
再遍历一遍，当总长度 len 减去 n，恰好等于循环的下标 i 时，就找到对应要删除的目标元素，将 prev 节点与 next 节点连接起来即可。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
int len = 0;
for(ListNode curr = head ; curr != null;){
len++;
curr = curr.next;
}
if(len == 0){
return null;
}
// remove head
if(len == n){
return head.next;
}
ListNode prev = null;
int i = 0;
for(ListNode curr = head; curr != null;){
i++;
prev = curr;
curr = curr.next;
if(i == (len – n)){
prev.next = curr.next;
}
}
return head;
}
}
Leetcode 测试的运行时间为 6ms，超过了 98.75% 的 java 代码。
解法二
这种解法，比较巧妙，没有想出来，查了网上的解法，思路如下：
思路
只需要循环一遍，定义两个指针，一个快指针，一个慢指针，让快指针的巧好领先于慢指针 n 步。当快指针到达 tail 节点时，满指针巧好就是我们需要删除的目标元素。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i < n; i++){
fast = fast.next;
}
if(fast == null){
return slow.next;
}
ListNode prev = null;
for(ListNode curr = slow; curr != null;){
// when fast arrived at tail, remove slow.
if(fast == null){
prev.next = curr.next;
break;
}
prev = curr;
curr = curr.next;
// move fast forward
fast = fast.next;
}
return head;
}
}
这段代码在 LeetCode 上的测试结果与解法一的一样。
这种解法与之前的 链表环检测 题目中都使用到了快慢指针，用来定位特定的元素。
相关练习
链表反转
链表环检测
有序链表合并
求链表的中间结点
参考资料
《数据结构与算法之美》
