【算法】单链表面试题

1.求单链表中有效节点的个数
//方法:获取到单链表的节点的个数(如果是带头节点的链表,不统计头节点)
    /**
     *
     * @param head 链表的头节点
     * @return 返回有效节点的个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        int length = 0;
        //定义一个辅助变量,这里我们没有统计头节点
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;  //遍历
        }
        return length;
    }
2.查找单链表中的倒数第k个节点【新浪】
//查找单链表中的倒数第k个节点【新浪】
    /*
    思路
    1.编写一个方法,接受head节点,同时接收一个index
    2.index表示的是倒数第index个节点
    3.先把链表从头到尾遍历,得到链表的总长度getLength
    4.得到size后,从链表的第一个开始遍历(size-index)个,就可以得到
    5.如果找到了就返回该节点,否则返回空
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        //如果链表为空,返回null
        if (head.next == null) {
            return null;  //没找到
        }
        //第一个遍历得到链表的长度
        int size = getLength(head);
        //第二次遍历 size-index 位置,就是倒数第k个节点
        //先做一个index的校验
        if (index <= 0 || index > size) {
            return null;
        }
        //定义一个辅助变量
        HeroNode cur = head.next;
        for (int i = 0; i < size-index; i++) {
            cur = cur.next;
        }
        return cur;
    }
3.单链表的反转【腾讯】

思路

1.先定义一个头节点 reverseHead = new HeroHead();

2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表 reverseHead 的最前端

3.原来的链表的 head.next = reverseHead.next

//将单链表反转【腾讯】
    public static void reverseList(HeroNode head) {
        //如果当前链表为空,或者只有一个节点,无需反转。直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义一个辅助指针,作用是帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0, "", "");
        //遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead 的最前端
        while (cur != null) {
            next = cur.next;  //先暂时保存当前节点的下一节点,因为后面需要使用
            cur.next = reverseHead.next;  //将cur的下一节点指向新的链表的最前端
            reverseHead.next = cur;  //将cur连接到新的链表上
            cur = next;  //让cur后移
        }
        //将head.next指向reverseHead.next,实现单链表的反转
        head.next = reverseHead.next;
    }
4.从尾到头打印单链表【百度】

思路

方式1:先将单链表进行反转操作,然后再遍历即可,这样做的问题是会破坏原来的单链表的结构

方式2:可以利用栈这个数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点,实现逆序打印的效果

举例演示栈的使用Stack

//演示栈Stack的基本使用
public class TestStack {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        //入栈
        stack.add("apple");
        stack.add("banana");
        stack.add("orange");

        //出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());  //pop就是将栈顶的元素取出
        }
    }
}
运行结果​​​​​​
/*
    使用方式2
    利用栈这个数据结构,将各个节点压入到栈中,
    然后利用栈的先进后出的特点,实现逆序打印的效果
     */
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {
            return;  //空链表,不能打印
        }
        //创建一个栈,将各节点压入栈
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        //将链表的所有节点压入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;  //cur后移,这样就可以压入下一个节点
        }
        //将栈中的节点进行打印,pop出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/869843.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

面试场景题系列--(2)短 URL 生成器设计:百亿短 URL 怎样做到无冲突?--xunznux

文章目录 面试场景题&#xff1a;短 URL 生成器设计&#xff1a;百亿短 URL 怎样做到无冲突&#xff1f;1. 需求分析2. 短链接生成算法2.1 自增法2.2 散列函数法2.3 预生成法 3. 部署模型3.1 其他部署方案 4. 设计4.1 重定向响应码4.2 短 URL 预生成文件及预加载4.3 用户自定义…

抖音直播弹幕数据逆向:websocket和JS注入

&#x1f50d; 思路与步骤详解 &#x1f575;️‍♂️ 思路介绍 首先&#xff0c;我们通过抓包工具进入的直播间&#xff0c;捕获其网络通信数据&#xff0c;重点关注WebSocket连接。发现直播弹幕数据通过WebSocket传输&#xff0c;这种方式比传统的HTTP更适合实时数据的传输。…

【LLM】-07-提示工程-聊天机器人

目录 1、给定身份 1.1、基础代码 1.2、聊天机器人 2、构建上下文 3、订餐机器人 3.1、窗口可视化 3.2、构建机器人 3.3、创建JSON摘要 利用会话形式&#xff0c;与具有个性化特性&#xff08;或专门为特定任务或行为设计&#xff09;的聊天机器人进行深度对话。 在 Ch…

聊聊基于Alink库的主成分分析(PCA)

概述 主成分分析&#xff08;Principal Component Analysis&#xff0c;PCA&#xff09;是一种常用的数据降维和特征提取技术&#xff0c;用于将高维数据转换为低维的特征空间。其目标是通过线性变换将原始特征转化为一组新的互相无关的变量&#xff0c;这些新变量称为主成分&…

基于opencv[python]的人脸检测

1 图片爬虫 这里的代码转载自&#xff1a;http://t.csdnimg.cn/T4R4F # 获取图片数据 import os.path import fake_useragent import requests from lxml import etree# UA伪装 head {"User-Agent": fake_useragent.UserAgent().random}pic_name 0 def request_pic…

idea springBoot启动时覆盖apollo配置中心的参数

vm options -Dorder.stat.corn“0/1 * * * * ?” 只有vm options, -D参数才能覆盖apollo参数 program arguments –key01val01 --key02val02 environment varibales envFAT;key02val02;key03val03

BGP选路之Preferred value

原理概述 当一台BGP路由器中存在多条去往同一目标网络的BGP路由时&#xff0c;BGP协议会对这些BGP路由的属性进行比较&#xff0c;以确定去往该目标网络的最优BGP路由&#xff0c;然后将该最优BGP路由与去往同一目标网络的其他协议路由进行比较&#xff0c;从而决定是否将该最优…

在 VM 虚拟机中安装 openEuler + 桌面

在 VM 虚拟机中安装 openEuler 1 介绍2 步骤语言Root 账户安装位置网络和主机名自动检索到【推荐】手动配置网络 软件选择安装完成登录测试网络curl ip / ping ipip link show / ip a如网络不通&#xff0c;可检查网卡状态和dns配置 安装命令设置以图形界面的方式启动【dde】第…

【屏显MCU】多媒体接口总结

本文主要介绍【屏显MCU】的基本概念&#xff0c;用于开发过程中的理解 以下是图层叠加示例 【屏显MCU】多媒体接口总结 0. 个人简介 && 授权须知1. 三大引擎1.1 【显示引擎】Display Engine1.1.1 【UI】 图层的概念1.1.2 【Video】 图层的概念1.1.3 图层的 Blending 的…

Linux——管理本地用户和组(详细介绍了Linux中用户和组的概念及用法)

目录 一、用户和组概念 &#xff08;一&#xff09;、用户的概念 &#xff08;二&#xff09;、组的概念 补充组 主要组 二、获取超级用户访问权限 &#xff08;一&#xff09;、su 命令和su -命令 &#xff08; 二&#xff09;、sudo命令 三、管理本地用户账户 &…

【OpenCV C++20 学习笔记】图片处理基础

OpenCV C20 图片处理基础 VS 2022 C20 标准库导入的问题头文件包含以及命名空间声明main函数读取图片读取检查显式图片写入图片 完整代码bug VS 2022 C20 标准库导入的问题 VS还没有完全兼容C20。C20的import语句不一定能正确导入标准库&#xff0c;所以必须要新建一个头文件专…

实时同步:使用 Canal 和 Kafka 解决 MySQL 与缓存的数据一致性问题

目录 1. 准备工作 2. 将需要缓存的数据存储 Redis 3. 监听 canal 存储在 Kafka Topic 中数据 1. 准备工作 1. 开启并配置MySQL的 BinLog&#xff08;MySQL 8.0 默认开启&#xff09; 修改配置&#xff1a;C:\ProgramData\MySQL\MySQL Server 8.0\my.ini log-bin"HELO…

Github个人网站搭建详细教程【Github+Jekyll模板】

文章目录 前言一、介绍1 Github Pages是什么2 静态网站生成工具3 Jekyll简介Jekyll 和 GitHub 的关系 4 Mac系统Jekyll的安装及使用安装Jekyll的简单使用 二、快速搭建第一个Github Pages网站三、静态网站模板——Chirpy1 个人定制 四、WordPress迁移到Github参考资料 前言 23…

机器学习笔记——决策树

定义 决策树是一种可以用来解决回归和分类的问题的算法 决策树使用树形结构&#xff0c;通过叶子节点上的条件层层推理&#xff0c;得到最终的结果 例如&#xff1a;通过上面的简单决策&#xff0c;我们可以通过形状这一条件决策出水果属于哪一类。 决策树的学习结果和取什么规…

在Windows安装、部署Tomcat的方法

本文介绍在Windows操作系统中&#xff0c;下载、配置Tomcat的方法。 Tomcat是一个开源的Servlet容器&#xff0c;由Apache软件基金会的Jakarta项目开发和维护&#xff1b;其提供了执行Servlet和Java Server Pages&#xff08;JSP&#xff09;所需的所有功能。其中&#xff0c;S…

ROS配置并同时驱动多个UVC相机(含功能包)

配置并同时驱动多个UVC相机&#xff0c;并将数据保存为ROS话题形式的bag文件。 ROS可以同时驱动多个UVC相机。要实现这个目标并将数据保存成ROS话题的形式&#xff0c;再保存为bag文件&#xff0c;可以按照以下步骤操作&#xff1a; 1. 安装必要的包 sudo apt-get update sud…

环境搭建-Docker搭建ClickHouse

Docker搭建ClickHouse 一、前言二、ClickHouse安装2.1 拉取镜像运行ClickHouse服务 三、测试安装3.1 进入clickhouse容器3.2 命令补充说明 四、测试连接五、设置CK的用户名密码 一、前言 本文使用的Docker使用Windows搭建&#xff0c;Linux版本的搭建方式一样。 Windows系统搭…

【笔记:3D航路规划算法】二、RRT*

目录 RRT*于RRT的不同之处1、路径优化&#xff1a;2、成本计算&#xff1a;3、重连线步骤&#xff1a; 图解1、初始化2、路径搜索3、效果展示 总结 3D路径规划是在三维空间中寻找从起点到终点的最短或最优路径的一种技术。它广泛应用于无人机导航、机器人运动规划、虚拟现实等领…

前台文本直接取数据库值doFieldSQL插入SQL

实现功能&#xff1a;根据选择的车间主任带出角色。 实现步骤&#xff1a;OA的“字段联动”功能下拉选项带不出表“hrmrolemembers”&#xff0c;所以采用此方法。 doFieldSQL("select roleid from HrmResource as a inner join hrmrolemembers as b on a.id b.resource…

c++笔记2

目录 2.2 栈底&#xff08;bottom&#xff09; } 大数乘大数 节点&#xff1a;包含一个数据元素及若干指向子树分支的信息 。 节点的度&#xff1a;一个节点拥有子树的数目称为节点的度 。 叶子节点&#xff1a;也称为终端节点&#xff0c;没有子树的节点或者度为零的节点…