欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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、输出结果如下:
java单链表(Linked List)查找单链表中的倒数第k个节点的应用示例

本文地址:https://blog.csdn.net/li1325169021/article/details/107474566