11-算法打卡-链表-删除链表的倒数第N个节点-leetcode(19)-第十一天

1 题目地址

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）19. 删除链表的倒数第 N 个结点 - 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例 1：[https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg]输入：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 进阶：你能尝试使用一趟扫描实现吗？https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

2 题目说明

给你一个链表，删除链表的倒数第 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

3 解题思路

双指针应用场景，如果要删除倒数第N个节点，让fast节点移动N步，然后在让slow和fast同时移动，直到fast指向链表尾部。删掉slow所指向的节点就可以了。

1 使用虚拟头节点，业务处理逻辑变的简单
2 定义快慢指针fast，slow， 指向虚拟头结点
3 fast先移动N+1步(fast节点领先slow节点N+1步，等fast指向链表末尾的时候，slow节点正好定位在倒数第N+1个节点)，举个例子N=2， fast节点先走3步，fast到链表末尾的时候，slow在倒数第4个节点上
4 使用链表移除slow的后一个节点即可

4 代码编写

4.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 dummyHead = new ListNode(-1, head);// 慢指针指向虚拟头节点ListNode slow = dummyHead;// 快指针指向虚拟头节点ListNode fast = dummyHead;// 快指针向前移动N+1步for (int i=0; i<=n; i++) {fast = fast.next;}// 移动到链表末端结束while (fast != null) {slow = slow.next;fast = fast.next;}// 中间变量暂存待删除的节点ListNode temp = slow.next;// 指向下下个节点slow.next = slow.next.next;// 待删除的节点的next置为null，后期会gc回收temp.next = null;return dummyHead.next;}
}