LeetCode 19. 删除链表的倒数第 N 个结点
LeetCode：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
题目描述
给你一个链表，删除链表的倒数第 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、两次遍历法，正序删除
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = head;
int size = 0;
if(head == null) return head;
// 第一次遍历, 求出链表长度
while(first != null) {
size++;
first = first.next;
}
int index = size - n; // 顺序要删除的下标, 起始下标为0
int count = 0; // 对链表头开始遍历的元素个数
first = head; // 重置链表头（求链表长度已遍历过一遍）
// 删除第一个元素
if(index == 0) {
first = first.next;
head = first; // 更改链表头
return head;
}
// 第二次遍历, 顺序删除链表第index个元素
// 1->2 3 4->5 删除倒数第3个元素
while(first != null) {
count++;
if(count == index) {
first.next = first.next.next;
break;
} else {
first = first.next;
}
}
return head;
}
}
说明：
此算法遍历了两次链表，第一次求链表长度，第二次删除第index个节点
时间复杂度：O(n) ，空间复杂度：O(1) ，只用了常量级的额外空间。
解法2、两次遍历，引入了最顶临时节点，简化首节点判断
注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 （size - n + 1）个结点，其中 size 是列表的长度。只要我们找到列表的长度 size，这个问题就很容易解决。
1）我们将添加一个最顶临时结点作为辅助，该结点位于列表头部。最顶临时结点用来简化了某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。
2）在第一次遍历中，我们找出列表的长度 size。然后设置一个指向最顶临时结点的指针，并移动它遍历列表，直至它到达第 （size - n）个结点那里。我们把第 （size - n）个结点的 next 指针重新链接至第 （size - n + 2）个结点，完成这个算法。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = head;
int size = 0;
ListNode top = new ListNode(0); // 增加了一个临时最顶节点
top.next = head; // 临时最顶节点指向head头, 解决删除头结点的问题
while(first != null) {
size++;
first = first.next;
}
int index = size - n;
first = top; // 指向最顶临时节点
while(index-- > 0) {
first = first.next;
}
first.next = first.next.next; // 最顶临时节点的next指向删除第index节点后的头结点
return top.next; // 返回删除后的头结点
}
}
复杂度分析
时间复杂度：O(n) ，该算法对列表进行了两次遍历，首先计算了列表的长度 其次找到第 （size - n）个结点。 操作执行了（2*size - n）步，时间复杂度为 O(n)
空间复杂度：O(1) ，只用了常量级的额外空间。
解法3、一次遍历，快慢两个指针相差步长为n，精妙
上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。
第一个指针从列表的开头向前移动 （n + 1） 步，而第二个指针将从列表的开头出发。
现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔（解决了倒数第n个节点的问题，从链表尾部向前计算，相差为n，精妙吧），直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点（非常关键，解题的核心，结束条件）。
我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head; // 快指针, 先遍历n个元素
ListNode slow = head; // 慢指针, 后开始遍历, 与fast同步
// fast 与 slow 距离为 n + 1
while(fast != null && n > 0) {
fast = fast.next;
n--;
}
// 1->2->3->4->5 n=2 1->2->3->5
while(fast != null && fast.next != null) { // fast不等于null, slow肯定也不等于null
fast = fast.next;
slow = slow.next;
}
if(fast == null) { // fast == null 是结束条件
head = head.next;
} else {
slow.next = slow.next.next;
}
return head;
}
}
复杂度分析
时间复杂度：O(n) ，该算法对含有 size 个结点的列表进行了一次遍历。因此时间复杂度为 O(n)
空间复杂度：O(1) ，我们只用了常量级的额外空间
解法4、一次遍历，删除倒数第n个元素，链表转数组存储，获取删除元素的前后元素，直观处理
核心思路：删除链表倒数第n个元素，即倒数第n个元素的前一个元素的next指向n元素的next
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = head;
Map<Integer, ListNode> map = new HashMap<Integer, ListNode>();
int size = 0;
int index = 0;
while(first != null) {
map.put(index++, first);
first = first.next;
}
size = map.size();
if(size == 0) return null;
// 1->2->3->4->5 n=2 1->2->3->5
if(n == size) {
head = head.next; // 删除链表第一个元素, 需修改链表头
} else {
map.get(size-n-1).next = map.get(size-n).next; // 倒数第n个元素的前一个元素next, 指向n的next
}
return head;
}
解法5、一次遍历，删除倒数第n个元素，运用栈的特性：后进先出顺序
因为是删除链表的倒数第n个元素，逆向思维：即删除压栈后，先弹出的第n个元素
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = head;
// 删除倒数第n个元素, 运用栈的后进先出特性, 来直观求解
Stack<ListNode> stack = new Stack<ListNode>();
while(first != null) {
stack.push(first);
first = first.next;
}
// 栈顶后入先出特性, 获取倒数的第n个元素
ListNode delNode = null; // 记录删除的元素
while(n-- > 0) {
delNode = stack.pop();
}
if(stack.size() > 0) {
stack.pop().next = delNode.next;
} else { // 栈为空, 即全部删除完了
head = head.next;
}
return head;
}
解法6、一次遍历，删除倒数第n个元素，优化解法5：凡事用栈解决的，用递归也可解决
核心思想：跟算法5类似，采用递归压栈，再出栈，代码非常简洁、统一、完美
注意：递归函数的变量，要在函数外赋值全局变量，例如 int count = 0; 在递归函数外
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
int count = 0;
public ListNode removeNthFromEnd(ListNode head, int n) {
// 2) 遇到最后一个元素为null, 则开始出栈, 返回
if(head == null) return null;
// 1) 先把全部元素压栈(类似于算法5的Stack)
// 1->2->3->4->5 n=2 1->2->3->5
head.next = removeNthFromEnd(head.next, n);
// 3) 递归一次加1, 类似于解法5的压栈后就开始出栈, 出栈的第n个元素即是删除倒数第n个元素
if(n == ++count) return head.next; // 返回删除元素n的next
return head;
}
}
晒一下成就：Java 执行用时 0ms，击败了 100%用户
总结
本文对一道算法题，用了六种解法，分别是：
1）两次遍历链表，把倒数第n个元素，转成了顺数第 size - n 个元素
2）优化算法1，新增了一个链表最顶部节点（假节点），解决删除头结点的判定问题
3）一次遍历，精妙设计快慢指针，二者相差为n个元素，fast快指针遍历到尾即结束
4）一次遍历，链表转数组，通过数组的下标直观进行链表的next链接
5）一次遍历，增加了Stack栈数据结构，把倒数第n个元素转成栈顶弹出第n个元素，更容易理解
6）一次遍历，凡是用栈能够实现的，大多也可以用递归函数实现（栈实现一般用深度递归队列也可实现）
刷算法题，注重数量的同时，更要注重质量，深入思考，不断优化递进，培养思维的深度
对一道题深度挖掘，举一反三，例如倒数第n个元素，用栈来实现，逆向思维，太美好啦
参考推荐：
Python 常用加密算法 base64, md5, sha1
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2021-02-05 18:21:56
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！