李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构学习--单链表面试题
Leefs
2020-01-27 PM
1338℃
0条
# 数据结构学习--单链表面试题 ### 前言 本篇将讲述之前新浪、百度、腾讯的单链表的面试题 ### 单链表面试题 (1)求单链表中有效节点的个数 **代码** ```java //方法:获取到单链表的节点的个数(如果是带头节点的链表,需求不统计头节点) 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; } ``` 需在`SingleLinkedList.class`类中添加返回头节点方法: ```java //返回头节点 public HeroNode getHead(){ return head; } ``` (2)查找单链表中的倒数第k个节点【新浪面试题】 > 思路: > > 1. 1.编写一个方法,接收head节点,同时接收一个index > > 2. 2.index表示是倒数第index个节点 > 3. 3.先把链表从头到尾遍历,得到链表的总的长度getLength > 4. 4.得到size后,我们从链表的第一个开始遍历(size-index)个,就可以得到 > 5. 5.如果找到了,则返回该节点,否则返回Null **代码** ```java 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; } //定义一个辅助变量, for循环定位到倒数的index HeroNode cur = head.next; for(int i=0;i
思路: > > 1. 1.先定义一个节点`reverseHead = new HeroNode();` > 2. 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表`reverseHead`的最前端。 > 3. 3.原来的链表的`head.next=reverseHead.next` **代码实现** ```java //将单链表反转 public static void reversetList(HeroNode head){ //如果当前链表为空,或者只有一个节点,无需反转,直接返回 if(head.next == null || head.next.next == null){ return; } //定义一个辅助的指针(变量),帮助我们遍历原来的链表 HeroNode cur = head.next; HeroNode next = null;//指向当前节点【cur】的下一个节点 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栈` **图像分析** ![04.链表面试题03.png][3] > 思路 > > 1. 1.上面的题的要求就是逆序打印单链表 > 2. 2.方式1:先将单链表进行反转操作,然后再遍历即可,这样的做的问题是会破坏原来的单链表的结构,不建议; > 3. 3.方式2:可以利用栈这个数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点,就实现了逆序打印的效果。 **代码实现** 测试Stack的使用 ```java //演示Stack的基本使用 public class TestStack { public static void main(String[] args) { Stack
stack = new Stack(); //入栈 stack.add("jack"); stack.add("tom"); stack.add("smith"); //出栈 while(stack.size()>0){ System.out.println(stack.pop());//pop就是将栈顶的数据取出 } } } ``` > 输出结果 ```java smith tom jack ``` **代码** ```java //方式2:可以利用栈这个数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点,就实现了逆序打印的效果. public static void reversePrint(HeroNode head){ if(head.next == null){ return;//空链表,不能打印 } //创建一个栈,将各个节点压入栈 Stack
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());//stack的特点是先进先出 } } ``` (5)合并两个有序的单链表,合并之后的链表依然有序 未完成 [1]: https://lilinchao.com/usr/uploads/2020/01/3952935960.png [2]: https://lilinchao.com/usr/uploads/2020/01/2992880065.png [3]: https://lilinchao.com/usr/uploads/2020/01/2973995764.png
标签:
数据结构
,
链表
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://www.lilinchao.com/archives/483.html
上一篇
数据结构学习--链表
下一篇
数据结构学习--双向链表
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
43
标签云
Sentinel
Flink
前端
容器深入研究
国产数据库改造
Elastisearch
Java
Nacos
Python
Yarn
SpringCloudAlibaba
工具
Spark SQL
正则表达式
序列化和反序列化
NIO
高并发
JavaScript
数学
SpringBoot
FastDFS
Git
Hbase
Linux
Tomcat
Livy
Spark
Stream流
Quartz
Spark RDD
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞