线性结构-链表应用

pr1 获取链表有效长度

思路：判空之后，定义计数器，遍历链表到链表末尾，返回计数器

前提：还是使用 线性结构-链表 文章中的HeroNode类
//定义一个heroNode
class HeroNode{
    //编号
    public int no;
    //英雄名字
    public String name;
    //英雄昵称
    public String nickName;
    //指向的下一个英雄
    public HeroNode next;

    public HeroNode(int no,String name,String nickName){
        this.no = no;
        this.nickName = nickName;
        this.name = name;
    }

    @Override
    public String  toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

代码：

/**
    * 获取链表有效长度
    * @return
    */
   public int getValidLength(){
       //判空,可以不判，但是判空之后如果满足条件直接就不用执行后面的了
       if(head.next==null){
           return 0;
       }
       //定义辅助变量遍历链表
       HeroNode temp = head.next;
       //定义计数器
       int count = 0;
       //遍历
       while (temp != null) {
           //计数器累加
           count++;
           //后移
           temp = temp.next;
       }

       return count;
   }

pr2获取倒数第k个元素

思路：遍历链表查找有效值个数；在遍历一次size=(count-k) || 快慢指针，这里只讲链表

代码：

/**
 * 查找单链表中倒数第k个节点
 * 思路：遍历链表查找有效值个数；在遍历一次size=(count-k)
 *
 * @param k 倒数第k个
 * @return
 */
public HeroNode getLastKthNode(int k) {
    //判空
    if(head.next==null){
        System.out.println("链表为空");
        return null;
    }
    //遍历找到有效值个数
    int count = getValidLength();
    //定义辅助变量
    HeroNode temp = head.next;
    //寻找边界值
    if (k <= 0 || k > count) {
        System.out.println("k小于0或大于链表有效值个数");
        return null;
    }
    //遍历
    for (int i = 0; i < (count - k); i++) {
        temp = temp.next;
    }

    //没找到返回null
    return temp;
}

测试代码：

public class SingleLinkedListDemo {
    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,"张飞","黑旋风");
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        System.out.println("===========================================");
        singleLinkedList1.addNodeInOrder(heroNode1);
        singleLinkedList1.addNodeInOrder(heroNode3);
        singleLinkedList1.addNodeInOrder(heroNode2);
        singleLinkedList1.addNodeInOrder(heroNode5);
        singleLinkedList1.addNodeInOrder(heroNode4);
        singleLinkedList1.showNode();
        System.out.println("===========================================");
        int validLength = singleLinkedList1.getValidLength();
        System.out.println("有效长度为"+validLength);
        int k = 2;
        HeroNode lastKthNode = singleLinkedList1.getLastKthNode(k);
        System.out.println("倒数第"+k+"个元素为:"+lastKthNode);
    }
}

打印结果：

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
倒数第2个元素为:HeroNode{no=4, name='林冲', nickName='豹子头'}