数据结构-链表练习(面试题)

1,翻转一个单链表

建立变量cur指向第二个节点,curN指向cur.next,将第二个节点的next改为head,head=cur这样实现,前两个节点顺序的翻转,第二个节点指向了第一个节点,之后cur向后移(cur=curN),curN也向后移,进行循环,直到所以节点的顺序都翻转

问:curN的作用是什么,为什么要这样定义?

答:因为进行反转时,这个节点的next要改为前一个节点的地址,所以这个节点和后一个节点就没有关系了,但是我们还需要找到后一个节点,依次进行翻转,所以设置变量,将后一个节点的地址提前记录下来

public void reverseList(){
    if (head==null){
        return;
    }
    ListNode cur=head.next;
    ListNode curNext=head.next.next;
    head.next=null;
    while (cur!=null){
        cur.next=head;
        head=cur;
        cur=curNext;
        if (curNext!=null){
        curNext=curNext.next;
        }
    }

}

2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点

用快慢指针法:快指针一次走两步,慢指针一次走一步,所以快指针走的是慢指针的两倍路程,所以慢指针指向的是链表的中间值

链表的节点分两种情况,一种为单数,另一种为双数,第一种,fast指向最后一个节点,slow指向中间节点,第二种,fast指向空,slow指向中间的靠右的节点

public ListNode returnMid(){
    if (head==null){
        return null;
    }
    ListNode slow=head;
    ListNode fast=head;
    while (fast!=null&&fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
    }
    return slow;
}

3, 输入一个链表,输出该链表中倒数第k个结点

用快慢指针法:快指针先走k-1个节点,然后快指针和慢指针一起向后走,直到快指针的下一个为null,则慢指针指向倒数第k个结点

首先要判断输入坐标的合法性,和链表为空的情况

private void KLegal(int k){
    if (k<=0||k>size()){
        throw new IndexException("输入的第k个节点,k输入异常");
    }
}
private void heedIsNull(){
    if (head==null){
        throw new IndexException("head为空,该链表没有节点");
    }
}
public  int kthToLast(int k){
    try {
        KLegal(k);
    }catch (IndexException e){
        e.printStackTrace();
    }
    try {
        heedIsNull();
    }catch (IndexException e){
        e.printStackTrace();
    }
    ListNode slow=head;
    ListNode fast=head;
    while ((k-1)!=0){
        fast=fast.next;
        k--;
    }
    while (fast.next!=null){
        fast=fast.next;
        slow=slow.next;
    }
    return slow.val;
}

4,将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

建立一个空节点,比较链表1,和链表2,的值将比较大的值的节点放到空节点的后面

然后再将p1与p2的val进行比较重复上述操作,知道一个链表的节点为0,直接将另一个链表剩余的节点直接放到新建的链表后面,最后将建立的空节点删除

public ListNode mergeTowLists(ListNode head1,ListNode head2){
    ListNode node=new ListNode(0);
    ListNode cur=node;
    ListNode b1=head1;
    ListNode p1=head2;
    while (b1!=null&&p1!=null){
        if (b1.val<p1.val){
            cur.next=b1;
            cur=cur.next;
            b1=b1.next;
        }else {
            cur.next=p1;
            cur=cur.next;
            p1=p1.next;
        }
    }
    if (b1==null){
        cur.next=p1;
    }else {
        cur.next=b1;
    }
    return node.next;

}

5,编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前

以x为界限,创立两个分区,遍历链表,将小于x的放到第一个分区,大于x的放到第二个分区,采用尾插法放置

public ListNode partition(int k) {
    ListNode b1 = null;
    ListNode b2 = null;
    ListNode p1 = null;
    ListNode p2 = null;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val < k) {
            if (b1 == null) {
                b1 = b2 = cur;
            } else {
                b2.next=cur;
                b2 = cur;
            }
        } else {
            if (p1 == null) {
                p1 = p2 = cur;
            } else {
                p2.next = cur;
                p2 = cur;
            }
        }
        cur = cur.next;
    }
    if (b1==null){
        return p1;
    }
    b2.next = p1;
    if (p1!=null){
        p2.next=null;
    }
    return b1;
}

6,判断回文

1,先用快慢指针,找到中间值,然后将中间值后面的节点翻转,然后,中间值以前的节点从前往后遍历,中间值以后的节点从后往前遍历,并对比节点的val是否相同,如果完全相同,则为回文,如果不相同,则不是

public boolean chkPalindrome(){
    if (head==null){
        return true;
    }
    ListNode slow=head;
    ListNode fast=head;
    while (fast!=null&&fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
    }
    ListNode cur=slow.next;
    ListNode curNext=cur.next;
    while (cur!=null){
        cur.next=slow;
        slow=cur;
        cur=curNext;
        if (curNext!=null){
            curNext=curNext.next;
        }
    }
    ListNode head1=head;
    while (slow!=head1&&head1.next!=slow){
        if (slow.val!=head1.val){
            return false;
        }
        slow=slow.next;
        head1=head1.next;
    }
    return true;
}

7, 输入两个链表,找出它们的第一个公共结点

先判断两个链表的长度,算出差值k,将长的链表向后走k步,然后,两个链表同时遍历,直到两个链表节点的next相等是,这next指向的节点就是公共节点

public  ListNode getIntersectionNode(ListNode head1,ListNode head2){
    ListNode p1=head1;//long
    ListNode p2=head2;
    int len1=0;
    int len2=0;
    while (p1!=null){
        p1=p1.next;
        len1++;
    }
    while (p2!=null){
        p2=p2.next;
        len2++;
    }
    int len=len1-len2;
     p1=head1;
     p2=head2;
    if (len1<len2){
        p1=head2;
        p2=head1;
        len=len2-len1;
    }
    while (len!=0){
        p1=p1.next;
        len--;
    }
    while (p1!=p2){
        p1=p1.next;
        p2=p2.next;
    }
    return p1;

}

8,成环的判断和成环的节点

成环的判断:快慢指针,快指针一次走两步,慢指针一次走一步,如果成环,快指针与慢指针总会相遇,所以当快指针等于慢指针时,则有环,如果遍历之后没有相遇,则没有环

public boolean isDetectCycle(){
    ListNode slow=head;
    ListNode fast=head;
    while (fast!=null&&fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
        if (fast==slow){
            return true;
        }
    }
    return false;
}

成环的节点:

有公式可推从头节点到成环节点的路程等于快指针与慢指针相遇的节点到成环节点的距离,所以将slow=head,快指针和慢指针同时走相遇的节点就是成环节点

public ListNode detectCycle(){
    ListNode slow=head;
    ListNode fast=head;
    while (fast!=null&&fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
        if (fast==slow){
           break;
        }
    }
    if (fast==null||fast.next==null){
        return null;
    }//排除没有环的情况
    slow=head;
    while (slow!=fast){
        slow=slow.next;
        fast=fast.next;
    }
    return slow;

}

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

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

相关文章

Git中单独的功能特性分支是什么含义

在Git中&#xff0c;一个"功能特性分支"&#xff08;通常简称为“特性分支”&#xff09;是指从主开发分支&#xff08;比如main或master&#xff09;独立出来的分支&#xff0c;专门用于开发一个新功能、修复一个bug&#xff0c;或者进行实验性的尝试。使用特性分支…

多用户商城思维导图

订单优惠逻辑计算 以上是下面功能结构图中的部分流程&#xff1a;

Qt QLCDNumber详解

1.简介 它提供了一个显示数字的显示屏控件&#xff0c;效果类似于现实世界中的液晶显示屏。它可以显示任何大小的数字。它可以显示十进制、十六进制、八进制或二进制数字。可以用setMode更改基数&#xff0c;用setSmallDecimalPoint更改小数点。 2.常用方法 以下是一些常用的…

Rust HashMap

一、HashMap是什么&#xff0c;怎么用 1、HashMap是什么 HashMap 也是 Rust 标准库中提供的集合类型&#xff0c;但是又与动态数组不同&#xff0c;HashMap 中存储的是一一映射的 KV 键值对&#xff0c;并提供了平均时间复杂度为 O(1) 的查询方法。 2、HashMap怎么用 &…

Verdin AM62 LVGL 移植

By Toradex胡珊逢 简介 LVGL 是一个免费、开源的图形库&#xff0c;能够在嵌入式设备如上使用 C/C 语言轻松绘制图形。由于这是一轻量级图形库&#xff0c;最初广泛被 MCU 处理器使用。随着功能完善&#xff0c;在性能和资源更充裕的 MPU 上也逐渐被使用。文章将介绍如何在 V…

币圈Cryptosquare论坛

Cryptosquare综合性资讯论坛汇集了币圈新闻、空投信息、社会热点以及与Web3相关的工作信息。让我们一起解锁加密世界的种种可能性&#xff0c;探索Cryptosquare论坛带来的精彩&#xff01; 币圈新闻板块&#xff1a; Cryptosquare论坛的币圈新闻板块是用户获取最新加密货币行业…

人工 VS AGV无人搬运机器人,AGV赋能中国智能制造

agv 机器人作为智能制造的重要抓手&#xff0c;正在渗透到各个传统行业&#xff0c;成为我国制造业转型升级的焦点。未来&#xff0c;智能AGV将不仅仅是简单的把货物搬运到指定的位置&#xff0c;而是要把5G技术、大数据、物联网、云计算等贯穿于产品的设计中&#xff0c;让智能…

【Java EE】日志框架(SLF4J)与门面模式

文章目录 &#x1f340;SLF4j&#x1f333;门面模式(外观模式)&#x1f338;门面模式的定义&#x1f338;门面模式的模拟实现&#x1f338;门面模式的优点 &#x1f332;关于SLF4J框架&#x1f338;引入日志门面 ⭕总结 &#x1f340;SLF4j SLF4J不同于其他⽇志框架,它不是⼀个…

LLM之RAG理论(十一)| 面向生产的RAG应用程序的12种调整策略指南

本文对文本RAG涉及到的主要12种关键“超参数”进行简单总结&#xff0c;主要包括摄取阶段&#xff08;数据清洗、数据分块、embedding模型选择、元数据过滤、多重索引和索引算法&#xff09;和推理阶段【检索和生成】&#xff08;查询转换、检索参数、高级检索策略、重排序、大…

React的数据Mock实现

在前后端分类的开发模式下&#xff0c;前端可以在没有实际后端接口的支持下先进行接口数据的模拟&#xff0c;进行正常的业务功能开发 1. 常见的Mock方式 2. json-server实现Mock 实现步骤&#xff1a; 项目中安装json-server npm i -D json-server准备一个json文件 {"…

大数据开发工作中的数仓设计(Hadoop,hive ,mysql )

1.HUE工具介绍使用 HUE是CDH提供一个hive和hdfs的操作工具&#xff0c;在hue中编写了hiveSQl也可以操作hdfs的文件 http://主机名字:端口号 hdfs的web访问端口 http://主机名字:端口号 hdfs的程序访问端口 进入后确保hdfs hive yarn 开启 在点击hue开启 在这里面也可以进行h…

记录k8s以docker方式安装Kuboard v3 过程

原本是想通过在k8s集群中安装kuboad v3的方式安装kuboard&#xff0c;无奈在安装过程中遇到了太多的问题&#xff0c;最后选择了直接采用docker安装的方式&#xff0c;后续有时间会补上直接采用k8s安装kuboard v3的教程。 1.kuboard安装文档地址&#xff1a; 安装 Kuboard v3 …

华为 huawei 交换机 配置 MUX VLAN 示例(汇聚层设备)

组网需求 在企业网络中&#xff0c;企业所有员工都可以访问企业的服务器。但对于企业来说&#xff0c;希望企业内部部分员工之间可以互相交流&#xff0c;而部分员工之间是隔离的&#xff0c;不能够互相访问。 如 图 6-4 所示&#xff0c; Switch1 位于网络的汇聚层&#xff0…

【百度Apollo】探索自动驾驶:小白教学如何使用 Dreamview 播放数据包

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《linux深造日志》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 文章目录 引入一、Dreamview 简介二、使用 Dreamview 具体步骤步骤一&#xff1a;进入 Apollo Docker 环境步骤二&#xff…

Qt QThreadPool线程池

1.简介 QThreadPool类管理一个QThread集合。 QThreadPool管理和重新设计单个QThread对象&#xff0c;以帮助降低使用线程的程序中的线程创建成本。每个Qt应用程序都有一个全局QThreadPool对象&#xff0c;可以通过调用globalInstance来访问该对象。 要使用其中一个QThreadPool…

VMware安装ubuntun虚拟机使用桥接模式无法上网问题解决

问题&#xff1a;最近准备使用VMware虚拟机搭建k8s集群服务&#xff0c;因为需要在同一个网段下&#xff0c;我使用桥接的方式&#xff0c;我发现主机在使用有线连接时虚拟机网络连接正常&#xff0c;但是使用无线网就显示连接不上网络。 解决方法 一、查看网络连接&#xff…

软考-信息系统项目管理师-论文技术架构模板(60天备考第26天)

分享一段信息系统项目管理师论文项目技术架构描述的万能模板&#xff0c;供大家参考。距离考试还有二十八天&#xff0c;如果论文写不好的可以加微进论文指导群学习论文写作。 该系统前端基于Vue开发&#xff0c;后端基于java开发&#xff0c;前后端分离部署。整体采用B/S架构&…

【论文阅读笔记】Frequency Perception Network for Camouflaged Object Detection

1.论文介绍 Frequency Perception Network for Camouflaged Object Detection 基于频率感知网络的视频目标检测 2023年 ACM MM Paper Code 2.摘要 隐蔽目标检测&#xff08;COD&#xff09;的目的是准确地检测隐藏在周围环境中的目标。然而&#xff0c;现有的COD方法主要定位…

java中的对象拷贝(包括BeanUtils和Mapstruct)

对象拷贝 借鉴&#xff1a; https://blog.csdn.net/weixin_43811057/article/details/122853749https://blog.csdn.net/weixin_42036952/article/details/105697234?spm1001.2101.3001.6650.8&utm_mediumdistribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogComme…

目标检测应用场景—数据集【NO.33】血细胞图像分类和检测数据集

写在前面&#xff1a;数据集对应应用场景&#xff0c;不同的应用场景有不同的检测难点以及对应改进方法&#xff0c;本系列整理汇总领域内的数据集&#xff0c;方便大家下载数据集&#xff0c;若无法下载可关注后私信领取。关注免费领取整理好的数据集资料&#xff01;今天分享…