萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第19题-删除链表的倒数第N个节点

发表于 2022-03-30 | 分类于 力扣刷题 | 0 | 阅读次数 90

题目描述

给你一个链表,删除链表的倒数第 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个节点,当第一个指针走到尾时,第二个指针所指向的节点恰好是倒数第n个节点。

Java代码题解

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode current = head;
        // 计算链表的节点数量
        int count = 0;
        while (current != null) {
            count++;
            current = current.next;
        }
        // 要删除的正序
        int rn = count - n + 1;
        current = head;
        // 如果删除第一个节点
        if (rn == 1) {
            head = current.next;
            current = null;
            return head;
        }
        count = 2;
        // 指针后移
        ListNode prior = current;
        current = current.next;
        while (current != null) {
            if (count == rn) {
                // 将前一个节点指向下一个节点
                prior.next = current.next;
                current = null;
                return head;
            }
            prior = current;
            current = current.next;
            count++;
        }
        return head;
    }
}

进阶版一次遍历:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个假头指向真头
        ListNode myHead = new ListNode(-1, head);
        // 创建双指针的前置
        ListNode fPrior = myHead;
        ListNode sPrior = myHead;
        // 创建双指针
        ListNode first = fPrior.next;
        ListNode second = sPrior.next;
        // 正序计数
        int count = 1;
        while (first != null) {
            // 第一个指针向前移动
            fPrior = first;
            first = first.next;
            // 当第一个指针走到正序第n个节点的时候第二个指针开始移动
            if (count > n) {
                // 第二个指针向前移动
                sPrior = second;
                second = second.next;
            }
            count++;
        }
        // 此时第二个指针所指向的节点就是倒数第n个节点
        // 删除第二个指针的节点
        if (sPrior.next == head) {
            // 如果第二个指针节点是真头节点做特殊处理
            head = head.next;
        } else {
            sPrior.next = second.next;
        }
        return head;
    }
}

复杂度分析

时间复杂度:O(n),n为链表的长度
空间复杂度:O(1)

# 算法 # 程序设计 # 力扣
力扣第16题-最接近的三数之和
力扣第18题-四数之和
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持