原文链接：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上的测试结果与解法一的一样。这种解法与之前的 链表环检测 题目中都使用到了快慢指针，用来定位特定的元素。相关练习链表反转链表环检测有序链表合并求链表的中间结点参考资料《数据结构与算法之美》