19.删除链表的倒数第N个节点
难度:中等
给你一个链表,删除链表的倒数第 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]
提示:
- 链表中结点的数目为
size
1 <= size <= 30
0 <= Node.val <= 100
1 <= n <= size
进阶:你能尝试使用一趟扫描实现吗?
解题思路
如果题目不要求我们只遍历一遍链表,但要求空间复杂度复杂度为 O(1) 的话,我们该怎么做呢?
我们往往不容易一开始就想到特别好的做法,暴力一点也无妨。
我的思路:
- 遍历一遍链表,同时计数,可以得到链表的总长度 size
- 那么我们需要倒数第 n 个元素,其实就是顺数第 size - n + 1 个元素
- 再遍历一遍链表,同时计数,但这次我们目标明确,找到第 size - n + 1 个元素
- 剩下的就是普通的删除链表内某节点的操作了
代码此处略去,但是复杂度应该是:
- 时间复杂度:O(2 * n) = O(n),因为遍历了两遍链表
- 空间复杂度:O(1)
这种做法空间复杂度很低,但没有满足题目要求只遍历一趟数组的要求。
我们能不能不预处理链表的长度呢?毕竟一趟遍历只为了一个 size,多少有点不值得。
双指针法
由于我们需要找到倒数第 n 个节点,因此我们可以使用两个指针 left 和 right 对链表进行遍历。
right 先从头到尾对链表进行遍历,当遍历到第 n 个节点的时候,我们要注意到一个点:此时剩下多少个元素没有遍历呢?答案是 size - n 个。
我们要删除的,是顺数第几个元素呢?刚好也是第 size - n + 1 个。
那么这个时候,让 left 也从链表头出发,两个指针开始同步往右边遍历,如此一来,当 right 指针走完剩下的 size - n 步时,left 指针也就走到了第 size - n 个元素。
尽管对于 指针位置信息 的处理可能得更加细致,但上述思路很清晰地表明我们可以找到需要删除的目标节点,而且 right 指针只需要走 size 步,left 指针只需要走 size - n 步,满足了题目一趟遍历的要求,同时空间复杂度也来到了常数级。
记住,我们设置快慢指针的目的是:让快慢指针相差 n 个结点,快指针走到尾部的时候,慢指针刚好处于倒数第 n 个节点的位置。
我的代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//虚拟头节点
ListNode dummy = new ListNode(0, head);
ListNode left = dummy;
ListNode right = dummy;
//right 走到第 n 个元素的位置
for (int i = 0; i < n; i++) {
right = right.next;
}
//left 开始和 right 同步移动
while (right.next != null) {
left = left.next;
right = right.next;
}
//要删除的是 left 的后一个节点
left.next = left.next.next;
return dummy.next;
}
}
时间复杂度:O(n)
空间复杂度:O(1)
总结
如果使用 C,C++ 编程语言的话,不要忘了还要从内存中删除这两个移除的节点。
当然如果使用 Java ,Python 的话就不用手动管理内存了。
注意虚拟头节点的引入,可以使代码逻辑更统一。