【力扣高频题】019.删除链表的倒数第 N 个结点

最近各个大厂的 招聘信息 已经陆续出来了，小伙伴们做好面试准备了么！！！

小编这里准备了一份 Java 八股文面试题，有需要的小伙伴可以 关注同名公众号，回复关键词 「1024」 获得。

速刷一遍，查漏补缺！！！

想 系统刷题 的小伙伴也可以点击链接了解下 八股文小程序 ，助力面试顺利，Offer 拿到手软！！！

---

言归正传，今天我们继续来学习 「力扣高频题」 系列。

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]

• 提示：
• 设链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

思路分析

链表结点的 删除 操作在算法题目中经常考察。

对于链表来说，要想删除某个结点，需要知道该结点的 前一个结点 的位置。

为了能够仅遍历一遍就能找到前一个结点，我们可以采用 双指针 的方法。

先让 快指针 走n+1步，之后与从头结点开始的 慢指针 一起向后运动。当快指针走到终点，指向空时，慢指针刚好来到了倒数第n+1个结点的位置，再进行删除操作即可。

代码

public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode cur = head;
    ListNode pre = null;
    while (cur != null) {
        // 大逻辑：每次 n--，cur 指针向后走
        // 当 n 走完减到 0 后，pre 和 cur 一起往后走
        n--;
        // 设置头，一起走
        if (n == -1) {
            pre = head;
        }
        if (n < -1) {
            pre = pre.next;
        }
        cur = cur.next;
    }
    // 链表结点总数不足 n 个，返回头结点
    if (n > 0) {
        return head;
    }
    // 若要删除的刚好是头结点，此时 n==0，cur为空，pre为空
    // 头结点删除，返回下一个结点
    if (pre == null) {
        return head.next;
    }
    // 将 前一个结点 直接连接到 后一个结点 上
    pre.next = pre.next.next;
    return head;
}

注意：

1. 若n超出了链表的长度，则应返回链表的头结点。

2. 若要删除的刚好是头结点，此时n == 0，cur为空，pre为空。应直接返回头结点的下一个结点。

---

「力扣高频题」 系列文章 已经更新不少了，有想刷力扣的小伙伴可以 收藏下方合集 逐题开刷~~~

~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~！！！
回复「1024」获取 Java 面试资源 ~
回复「ACM紫书」获取 ACM 算法书籍 ~
回复「算法导论」获取 算法导论第3版 ~

在看 + 转发

让你的小伙伴们一起来学算法吧！！

原文地址：https://blog.csdn.net/weixin_46879314/article/details/140657048

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！