19. 删除链表的倒数第 N 个结点
快慢指针
思路
快指针先走N步,然后快慢指针以相同速度向右遍历链表,当快指针指向最后一个结点时,慢指针指向倒数第N个结点的前驱结点。
补充
涉及到链表的插入与删除操作增加一个虚拟头结点准没错!
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1); // 虚拟头结点dummy.next = head;ListNode fast = dummy; // 快指针ListNode slow = dummy; // 慢指针// 快指针先走n步while (n != 0) {fast = fast.next;n--;}// 快指针指向最后一个结点时,慢指针指向倒数第N个结点的前驱结点while (fast.next != null) {fast = fast.next;slow = slow.next;}// 删除结点slow.next = slow.next.next;return dummy.next;}
}
递归
专门想了一下能否用递归,没想出来😿
递归思路模版
专注于当前层递归,思考下面3个问题:
- 1、找整个递归的终止条件:递归应该在什么时候结束?
- 2、找返回值:应该给上一级返回什么信息?
- 3、本级递归应该做什么:在这一级递归中,应该完成什么任务?
1:p = null 时,表明当前递归的结点 p 指向链表末尾(尾结点后面),返回当前结点 p 的深度 depth = 0;
2:向上一层返回当前层结点的深度;
3:递归调用函数处理下一个结点开头的子链表,并接收下一层递归调用的返回值 depth 。若 depth = n,表明下一层调用的结点深度是 n (即倒数第 n 个结点),执行删除操作。
暂未解决
哑结点的作用是什么?
应该与虚拟结点作用相同:删除的可能是头结点,通过添加哑结点,使头结点与其他结点的删除操作相同。
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 创建哑结点,并连到原链表ListNode s = new ListNode(-1, head);// 递归调用remove(),从哑结点开始进行删除操作remove(s, n);// 返回新链表的头(去掉可能的哑结点)return s.next;}// 删除链表p的倒数第 n 个结点,并返回结点 p 的深度 depth(链表 p 的结点数量,即结点 p 在原链表中是倒数第 depth 个结点)public int remove(ListNode p, int n) {// 递归出口:当 p 为空时,表示 p 指向尾结点的后面,返回0if (p == null) return 0;// 递归体int depth = remove(p.next, n);if (depth == n) { // 若下一层调用的结点是倒数第 n 个结点,则删除p.next = p.next.next;}// 当前层传递给上一层的递归调用的信息return depth + 1; }
}