【LeetCode热题100】打卡第10天：删除链表倒数第N个节点网站首页 技术教程

【LeetCode热题100】打卡第10天：删除链表倒数第N个节点

知识汲取者 2024-07-18 06:01:02

简介【LeetCode热题100】打卡第10天：删除链表倒数第N个节点

文章目录

删除链表倒数第N个节点

删除链表倒数第N个节点

⛅前言

大家好，我是知识汲取者，欢迎来到我的LeetCode热题100刷题专栏！

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。在此专栏中，我们将会涵盖各种类型的算法题目，包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等，并会提供详细的解题思路以及Java代码实现。如果你也想刷题，不断提升自己，就请加入我们吧！QQ群号：827302436。我们共同监督打卡，一起学习，一起进步。

博客主页?：知识汲取者的博客

LeetCode热题100专栏?：LeetCode热题100

Gitee地址?：知识汲取者 (aghp) - Gitee.com

Github地址?：Chinafrfq · GitHub

题目来源?：LeetCode 热题 100 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

PS：作者水平有限，如有错误或描述不当的地方，恳请及时告诉作者，作者将不胜感激

?题目

原题链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

在这里插入图片描述

?题解

解法一：模拟

这个题是考察数据结构，主要是考察你对链表的操作，相对而言算比较简单的题目?，唯一需要注意的点是要单独处理删除头节点的情况，防止出现NPE，相信你看完代码应该能够很容易理解的

/**
 * @author ghp
 * @title 删除链表倒数第N个节点
 */
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) {
        // 遍历得到链表的长度
        int len = 0;
        ListNode tempNode = head;
        while (tempNode != null) {
            tempNode = tempNode.next;
            len++;
        }
        // 判断删除的节点是否是头节点（防止后面出现NPE）
        if (len == 1 || len == n) {
            return head.next;
        }
        // 获取要删除链表的前一个节点
        int i = len - n - 1;
        tempNode = head;
        while (i != 0) {
            tempNode = tempNode.next;
            i--;
        }
        // 删除节点
        tempNode.next = tempNode.next.next;

        return head;
    }
}

复杂度分析：

时间复杂度： $O (n)$
空间复杂度： $O (1)$

其中 $n$ 为链表中节点的个数

附LeetCode官方代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。