java单链表(Linked List)查找单链表中的倒数第k个节点的应用示例
程序员文章站
2022-07-10 19:15:10
一、查找单链表中的倒数第k个节点的代码示例1、定义一个人员节点类,每一个PersonNode对象就是一个节点package com.rf.springboot01.dataStructure.singleLinkedList;/** * @description: 定义一个人员节点类,每一个PersonNode对象就是一个节点 * @author: xiaozhi * @create: 2020-07-15 16:44 */public class PersonNode { pu...
一、查找单链表中的倒数第k个节点的代码示例
1、定义一个人员节点类,每一个PersonNode对象就是一个节点
package com.rf.springboot01.dataStructure.singleLinkedList;
/**
* @description: 定义一个人员节点类,每一个PersonNode对象就是一个节点
* @author: xiaozhi
* @create: 2020-07-15 16:44
*/
public class PersonNode {
public int num;//编号
public String name;//名称
public String aliasName;//别名
public PersonNode next;//指向下一个节点
//构造器
public PersonNode(int num, String name, String aliasName) {
this.num = num;
this.name = name;
this.aliasName = aliasName;
}
//重写toString方法
@Override
public String toString() {
return "PersonNode{" +
"num=" + num +
", name='" + name + '\'' +
", aliasName='" + aliasName + '\'' +
'}';
}
}
2、创建一个单链表管理人员节点
package com.rf.springboot01.dataStructure.singleLinkedList;
/**
* @description: 创建一个单链表管理人员节点
* @author: xiaozhi
* @create: 2020-07-16 22:04
*/
public class SingleLinkedList {
//先初始化一个头结点,头节点位置固定,不存放任何数据,作用是表示链表的头节点
private PersonNode head =new PersonNode(0,"","");
public PersonNode getHead() {
return head;
}
//在链表的指定位置添加节点数据
public void addByNum(PersonNode personNode){
PersonNode temp=head;
boolean flag=false;//插入的编号是否存在,默认不存在
while(true){
if(temp.next==null){//已经在链表的尾部
break;
}
if(temp.next.num >personNode.num){//找到位置,在temp后添加
break;
}
if(temp.next.num==personNode.num){//编号已经存在,不能添加
flag=true;
break;
}
temp=temp.next;//后移,遍历
}
if(flag){
System.out.printf("添加的人员编号%d已经存在,不能添加\n",personNode.num);
}else{
//添加数据到链表中,temp后的位置
personNode.next=temp.next;
temp.next=personNode;
}
}
//显示链表
public void show(){
//判断链表是否为空
if(head.next==null){
System.out.println("链表为空");
return;
}
//因为头节点不能动,所以需要一个临时变量来遍历
PersonNode temp=head.next;
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp向后移动
temp = temp.next;
}
}
/**
* @Description: 查找单链表中的倒数第k个节点
* @Param: PersonNode 表示head节点;index 表示需要查找的倒数第几个节点个数
* @Author: xz
* @return: PersonNode对象
* @Date: 2020/7/20 21:15
*/
public static PersonNode getLastIndexNode(PersonNode head,int index){
//判断链表是否为空,如果是返回null
if(head.next == null){
return null;
}
//1、第一次遍历,单链表获取链表的长度(节点个数)
int size = getCount(head);
//2、校验index
if(index<0 || index>size){
return null;
}
//2、第二次再次遍历(size-index)的位置,获取倒数的第K个节点
//(size-index)比如3个节点,获取倒数第1个节点,倒数第1个节点的位置=总节点数3-倒数第一个节点数1=2 即需要从第一个节点开始移动2个节点位置
PersonNode temp =head.next;//定义一个临时变量
for(int i=0;i<size-index;i++){
temp =temp.next;
}
return temp;
}
/**
* @Description: 获取单链表节点的有效个数(如果是带有头节点的链表,需求不统计头节点)
* @Param: head链表的头节点
* @Author: xz
* @return: 单链表节点的有效个数
* @Date: 2020/7/16 21:51
*/
public static int getCount(PersonNode head){
if(head.next==null){//空链表
return 0;
}
int count=0;
PersonNode temp=head.next;//定义一个辅助变量
while(temp !=null ){
count++;
temp=temp.next;//节点后移
}
return count;
}
}
3、定义一个测试类
package com.rf.springboot01.dataStructure.singleLinkedList;
/**
* @description:
* @author: xiaozhi
* @create: 2020-07-16 22:05
*/
public class SingleLinkedListTest {
public static void main(String[] args) {
//创建节点
PersonNode personNode1 = new PersonNode(1, "张三", "小张");
PersonNode personNode2 = new PersonNode(2, "李四", "小李");
PersonNode personNode3 = new PersonNode(3, "王五", "小王");
PersonNode personNode4 = new PersonNode(4, "赵二", "小赵");
System.out.println("添加链表节点数据============");
//添加链表节点数据
SingleLinkedList s = new SingleLinkedList ();
s.addByNum(personNode1);
s.addByNum(personNode4);
s.addByNum(personNode2);
s.addByNum(personNode3);
//显示所有链表节点
s.show();
//单链表中的倒数第K个节点
PersonNode personNode=SingleLinkedList.getLastIndexNode(s.getHead(),2);
System.out.println("单链表中的倒数第2个节点="+personNode);
}
}
4、输出结果如下:
本文地址:https://blog.csdn.net/li1325169021/article/details/107474566