数据结构和算法之单链表练习
三道大厂面试题：
【新浪面试题】查找单链表中的倒数第k个结点
【腾讯面试题】单链表的反转
【百度面试题】从尾到头打印单链表
1、先上神器：
lombok，在pom里面加入依赖，并在idea中下载lombok插件，然后就可以直接使用啦~
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<version>1.18.16</version>
</dependency>
2、用一个heroNode类模拟节点
@Data
@NoArgsConstructor
class HeroNode{
private int no;
private String name;
private String nickname; //昵称
private HeroNode next;//指向下一个节点编号
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
public String toString(){
return"HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
//重写tostring方法，方便展示输出数据
}
}
3、单链表方法的实现
//链表操作
class SingleLinkedTest{
//链表的头部固定，定义一个头节点，数据为空
private HeroNode head = new HeroNode(0,"","");
public HeroNode getHead() {
return head;
}
//将节点挂上链表
public void addNode(HeroNode heroNode){
//先找到尾节点，然后把新节点挂到尾节点上
//定义辅助节点temp
HeroNode temp = head;
while (true){
if (temp.getNext() == null){ //当辅助节点的下一个节点为空时，表示找到了最后一个节点
break;
}
temp = temp.getNext();
}
temp.setNext(heroNode);
}
//有序的将节点加入链表
public void addOrderNode(HeroNode heroNode){
//定义辅助节点temp
HeroNode temp = head;
while (true){
if (temp.getNext() == null){ //当辅助节点的下一个节点为空时，表示已经到了最后一个节点
temp.setNext(heroNode);
break;
}
//当辅助节点的下一个节点的编号大于当前编号，则找到了插入的位置
if (heroNode.getNo() < temp.getNext().getNo()){
heroNode.setNext(temp.getNext());
temp.setNext(heroNode);
break;
}
temp = temp.getNext();
}
}
//获取节点个数，不包括头结点
public void getNodeCount(){
HeroNode temp = head;
int count = 0;
while (true){
if (temp.getNext() == null){
break;
}
count++;
temp = temp.getNext();
}
System.out.println("节点的个数为："+count);
}
//节点反转
public SingleLinkedTest reversalLink(SingleLinkedTest singleLinkedTest){
SingleLinkedTest singleLinkedTestTemp = new SingleLinkedTest();
HeroNode temp ;//辅助节点
HeroNode temp01 = singleLinkedTest.getHead().getNext(); //要反转链表的头部
while (true){
if (temp01 == null){
break; //旧链表空了，表示全部反转完了
}
//反转链接，所以所有新获取的节点，每次都放到head后面
temp = singleLinkedTestTemp.getHead().getNext(); //总是指向新链表的下一个节点
singleLinkedTestTemp.getHead().setNext(temp01);
temp01=temp01.getNext();
singleLinkedTestTemp.getHead().getNext().setNext(temp);
}
return singleLinkedTestTemp;
}
//获取倒数第K个节点
public void getKNode(SingleLinkedTest singleLinkedTest,int k){
int count = 0;
HeroNode temp = singleLinkedTest.getHead(); //辅助节点
if(temp.getNext() == null){
System.out.println("链表为空，无法获取");
return;
}
while (true){
if (count == k){
System.out.printf("倒数第%d个节点是：\n"+temp,k);
break;
}
temp = temp.getNext();
count++;
}
}
//展示链表所有数据
public void showNode(SingleLinkedTest singleLinkedTest){
//定义辅助节点temp
HeroNode temp = singleLinkedTest.getHead();
if (temp.getNext() == null){
System.out.println("当前链表为空~");
return;
}
while (true){
if (temp.getNext() == null){
break;
}
System.out.println(temp.getNext());
temp = temp.getNext();
}
}
}
4、开始测试
public class SingleLinked {
public static void main(String[] args) {
HeroNode heroNode1 = new HeroNode(1, "一号", "小明");
HeroNode heroNode2 = new HeroNode(2, "二号", "小红");
HeroNode heroNode3 = new HeroNode(3, "三号", "小君");
HeroNode heroNode4 = new HeroNode(4, "四号", "小帅");
HeroNode heroNode5 = new HeroNode(5, "五号", "小鹿");
SingleLinkedTest singleLinkedTest = new SingleLinkedTest();
// singleLinkedTest.addNode(heroNode1);//按照执行顺序添加节点
// singleLinkedTest.addNode(heroNode2);
// singleLinkedTest.addNode(heroNode3);
singleLinkedTest.addOrderNode(heroNode1);//有序的添加节点
singleLinkedTest.addOrderNode(heroNode5);
singleLinkedTest.addOrderNode(heroNode4);
singleLinkedTest.addOrderNode(heroNode3);
singleLinkedTest.addOrderNode(heroNode2);
singleLinkedTest.showNode(singleLinkedTest);//链表数据展示
//求链表节点个数
singleLinkedTest.getNodeCount();
//求倒数第K个节点 + 链表反转 + 从尾到头打印
SingleLinkedTest singleLinkedTestReversal =
singleLinkedTest.reversalLink(singleLinkedTest);//得到反转后的链表
singleLinkedTest.showNode(singleLinkedTestReversal);//展示反转后的链表数据
singleLinkedTest.getKNode(singleLinkedTestReversal,5);//得到反转后的链表中第5条数据
}
}
5、结果：
HeroNode[no=1,name=一号,nickname=小明]
HeroNode[no=2,name=二号,nickname=小红]
HeroNode[no=3,name=三号,nickname=小君]
HeroNode[no=4,name=四号,nickname=小帅]
HeroNode[no=5,name=五号,nickname=小鹿]
节点的个数为：5
HeroNode[no=5,name=五号,nickname=小鹿]
HeroNode[no=4,name=四号,nickname=小帅]
HeroNode[no=3,name=三号,nickname=小君]
HeroNode[no=2,name=二号,nickname=小红]
HeroNode[no=1,name=一号,nickname=小明]
倒数第5个节点是：
HeroNode[no=1,name=一号,nickname=小明]
发表于 2021-2-23 23:04
|
发表于 2021-2-24 10:29
