|
题一:统计链表节点个数
题二:查倒数第K个节点
题三:倒序遍历
题四:反转链表★★★★★
?测试类
import com.atguigu.linkedlist.HeroNode;
import com.atguigu.linkedlist.SingleLinkedList;
import java.util.Scanner;
public class interview_full {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
char key = ' ';//用来接收用户传入的指令
Scanner scanner = new Scanner(System.in);
boolean flag = true;
while (flag){
System.out.println("=====1.显示链表=====");
System.out.println("=====2.退出程序=====");
System.out.println("=====3.添加数据到链表=====");
System.out.println("=====4.查看某个节点=====");
System.out.println("=====5.删除某个节点=====");
System.out.println("=====6.修改某个节点=====");
System.out.println("=====7.统计节点个数=====");
System.out.println("=====8.查找单链表中的正数第K个节点=====");
System.out.println("=====9.查找单链表中的倒数第K个节点=====");
System.out.println("=====a.链表反转=====");
key = scanner.next().charAt(0);
switch (key){
case '1':
singleLinkedList.show();
break;
case '2':
flag = false;
break;
case '3':
System.out.println("请创建节点对象:id,姓名,昵称 中间用逗号分隔");
String next = scanner.next();
String[] split = next.split(",");
HeroNode insert = new HeroNode(Integer.parseInt(split[0]), split[1], split[2]);
singleLinkedList.addById(insert);
break;
case '4':
System.out.println("请输入查找的id");
int id = scanner.nextInt();
System.out.println(singleLinkedList.find(id).next);
break;
case '5':
System.out.println("请输入删除的id");
int id1 = scanner.nextInt();
singleLinkedList.remove(id1);
break;
case '6':
System.out.println("请输入修改的节点对象:id,姓名,昵称 中间用逗号分隔");
String next1 = scanner.next();
String[] split1 = next1.split(",");
HeroNode insert1 = new HeroNode(Integer.parseInt(split1[0]), split1[1], split1[2]);
singleLinkedList.change(insert1);
break;
case '7':
System.out.println("链表中有" + singleLinkedList.count() + "个节点");
break;
case '8':
System.out.println("请输入要找正数第几个");
int k = scanner.nextInt();
System.out.println(singleLinkedList.findK(k));
break;
case '9':
System.out.println("请输入要找倒数第几个");
int k1 = scanner.nextInt();
System.out.println(singleLinkedList.findLastK(k1));
break;
case 'a':
singleLinkedList.turnOver();
break;
default:
System.out.println("请输入正确的指令");
}
}
}
}
链表对象类
public class SingleLinkedList{
//定义头结点,指向链表头位置,因为是不存放数据的,所以用一个空的HeroNode来占位.
public HeroNode header = new HeroNode(0,"","");
//显示链表
public void show(){
if (isEmpty()){
System.out.println("链表为空");
}else{
System.out.println("============显示链表============");
HeroNode tmp = header.next;
while (true){
//每次循环,都要判断tmp是否为null,如果为null,说明已经没有节点了,要退出循环
if (tmp == null){
break;
}
System.out.println(tmp);
tmp = tmp.next;
}
}
}
//判断链表是否为空
public boolean isEmpty(){
return header.next == null;
}
//根据节点的id来添加(有位置的添加)
//还是需要用到临时变量来寻找添加位置的前一个节点
//如果要添加的位置已存在node,则返回失败
//把前一个节点的next指向新增的节点,新增的节点的next指向前一个节点的原next的指向的节点
public void addById(HeroNode node){
HeroNode tmp = header;
while (true){
if (tmp.next == null){
//说明此时tmp后面已经没有节点了,此时就可以插入到tmp的后面(需要node的no.大于此时队列中的任何一个no.)
break;
}
//需要用tmp的next指向的节点的id,与要插入的节点的id,来进行比较
if (tmp.next.no > node.no){
//此时可以认为插入位置已经被找到了
break;
}else if (tmp.next.no == node.no){
//表示已存在相同的id号了
System.out.println(node.no + "已存在");
return;
}
tmp = tmp.next;
}
//跳出循环的时候,此时tmp就是插入位置的前一个节点了
node.next = tmp.next;
tmp.next = node;
System.out.println("==========按照id插入成功=========");
}
//查找某个节点
public HeroNode find(int id) {
//还是要借助临时变量
HeroNode tmp = this.header;
while (true){
if (tmp.next == null || tmp.next.no == id){
//为了增加这个方法的复用性,我们返回要找的节点的上一个节点
//这样这个方法就可以被在删除,修改中调用了
return tmp;
}
tmp = tmp.next;
}
}
public void change(HeroNode node) {
//找到原节点的前一个节点
HeroNode frontNode = find(node.no);
//修改指向
node.next = frontNode.next.next;
frontNode.next = node;
System.out.println("执行修改完成");
}
//删除节点
public void remove(int id) {
HeroNode front = find(id);
HeroNode target = front.next;
front.next = target.next;
System.out.println("执行删除完成");
}
//统计个数
public int count(){
HeroNode tmp = header.next;
if (isEmpty()){
return 0;
}
int sum = 1;
while (tmp.next != null){
sum ++;
tmp = tmp.next;
}
return sum;
}
//查找正数第K个节点
public HeroNode findK(int k){
int count = count();
if (count < k){
System.out.println("不存在该节点");
return null;
}
HeroNode tmp = this.header.next;
int total = 1;
while (total != k){
tmp = tmp.next;
total ++;
}
return tmp;
}
//查找倒数第K个节点
public HeroNode findLastK(int k){
int count = count();
if (count < k){
return null;
}
else {
return findK(count - k + 1);
}
}
//反转链表
public void turnOver() {
int count = count();
if (isEmpty()){
System.out.println("队列为空");
return;
}
if (count() == 1){
show();
return;
}
HeroNode newHeader = new HeroNode(0, "", "");
HeroNode tmp = header.next;
HeroNode tmp1 = null;
while (tmp.next != null) {
//目前遍历到tmp这个节点
tmp1 = tmp.next;
//把tmp的下一个接到新的头结点上,就相当于变成了一个栈,从左向右push进去,先进后出.
tmp.next = newHeader.next;
//别忘记修改一下新头指针的指向,指向新来的
newHeader.next = tmp;
tmp = tmp1;
}
header = newHeader;
show();
}
//反向遍历链表
public void overshow() {
int count = count();
for (int i = 1; i < count + 1; i++) {
System.out.println(findLastK(i));
}
}
}
|