算法基础04：单链表面试题

单链表几个面试题

求单链表中有效节点个数

package com.algorithm.linkedlist;


/**
 * 单项链表
 * 直接添加到链表尾部
 * 是根据插入顺序而排序，不会根据序号排序
 *
 * @author：XMD
 * @date: 8.8.22
 */
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, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode4);

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        //显式
        singleLinkedList.list();

        HeroNode newHeroNode4 = new HeroNode(2, "小炉子", "玉观音");
        singleLinkedList.update(newHeroNode4);

        System.out.println("<<<<<<<<<<<<<<");

        singleLinkedList.list();
        System.out.println("<<<<<<<<<<<<<<");

        singleLinkedList.delete(2);
        singleLinkedList.delete(4);
        singleLinkedList.list();

        System.out.println("<<<<<<<<<<<<<<");
        int length = getLength(singleLinkedList.getHead());
        System.out.println(length);


    }


    /**
     * 方法，获取单链表的节点个数（如果是待头节点的链表，需求不需要统计）
     */
    public static int getLength(HeroNode heroNode){
        int length = 0;
        if (heroNode.next == null){
            //说明为空链表
            return length;
        }

        //这里没有统计头节点
        HeroNode cur = heroNode.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {
    /**
     * 先初始化一个头节点，头节点不要动，不存放具体数据
     */
    private HeroNode head = new HeroNode(0, "", "");
    public HeroNode getHead(){
        return head;
    }

    /**
     * 第一种添加方式
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入指定位置
     * 如果有这个排名，则添加失败，并给出提示
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，是否插入不了
        HeroNode temp = head;
        //标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            //说明到链表的最后了
            if (temp.next == null) {
                break;
            }
            //位置找到，就在temp的后面插入
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                //添加的节点已经存在
                flag = true;
                break;
            }
            //后移动
            temp = temp.next;
        }
        if (flag) {
            System.out.println("节点已经存在");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }




    /**
     * 修改结点信息，根据no编号修改，no不能修改
     * 说明
     * 1.根据newHeroNode的no来修改即可
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;//已经遍历完
            }
            if (temp.no == newHeroNode.no) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.println("没有找到");
        }

    }


    /**
     * 删除节点
     * 1。head不能动，因此我们需要一个temp辅助节点找到需要删除的前一个节点
     * 2.说用我们在比较时，是temp。next.no 和需要删除的节点的no比较
     */
    public void delete(int no) {
        HeroNode temp = head;
        boolean boo = false;
        while (true) {
            if (temp.next == null) {
                //已经到最后
                break;
            }

            if (temp.next.no == no) {
                //找到需要删除的前一个节点
                boo = true;
                break;
            }
            temp = temp.next;
        }

        if (boo) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到这个节点");
        }
    }


    /**
     * 显式链表（遍历）
     */
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因为我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表的最后
            if (temp == null) {
                break;
            }
            //输出结点信息
            System.out.println(temp);
            //将节点后移
            temp = temp.next;
        }
    }


}

/**
 * 定义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.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "no=" + no + ", name=" + name + ", nickname=" + nickname;
    }
}

查找单链表中的倒数第K个结点

package com.algorithm.linkedlist;


/**
 * 单项链表
 * 直接添加到链表尾部
 * 是根据插入顺序而排序，不会根据序号排序
 *
 * @author：XMD
 * @date: 8.8.22
 */
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, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode4);

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        //显式
        singleLinkedList.list();

        HeroNode newHeroNode4 = new HeroNode(2, "小炉子", "玉观音");
        singleLinkedList.update(newHeroNode4);

        System.out.println("<<<<<<<<<<<<<<");

        singleLinkedList.list();
        System.out.println("<<<<<<<<<<<<<<");

//        singleLinkedList.delete(2);
//        singleLinkedList.delete(4);
//        singleLinkedList.list();
//
//        System.out.println("<<<<<<<<<<<<<<");
        int length = getLength(singleLinkedList.getHead());
        System.out.println(length);

        System.out.println("<<<<<<<<<<<<<<");
        HeroNode heroNode = findHeroNodeByIndex(singleLinkedList.getHead(), 3);
        System.out.println(heroNode);

    }


    /**
     * 方法，获取单链表的节点个数（如果是待头节点的链表，需求不需要统计）
     */
    public static int getLength(HeroNode heroNode){
        int length = 0;
        if (heroNode.next == null){
            //说明为空链表
            return length;
        }

        //这里没有统计头节点
        HeroNode cur = heroNode.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }


    /**
     * 查找单链表中的倒数第K个结点【新浪面试题】
     * 思路
     * 1，编写一个方法，接收head节点，同时接收一个index
     * 2.index表示是倒数第index个结点
     * 3.先把链表从头到尾遍历，得到链表的总长度
     * 4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
     * 5.如果找到，则返回节点，否则返回null
     */

    public static HeroNode findHeroNodeByIndex(HeroNode head,int index){
        if (head.next == null){
            //没有找到
            return null;
        }
        //链表的长度
        int size = getLength(head);
        //如果index等于0，或者index的长度大于链表的长度，就返回null
        if (index <= 0 || index > size){
            return null;
        }
        //定义辅助变量
        HeroNode temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {
    /**
     * 先初始化一个头节点，头节点不要动，不存放具体数据
     */
    private HeroNode head = new HeroNode(0, "", "");
    public HeroNode getHead(){
        return head;
    }

    /**
     * 第一种添加方式
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入指定位置
     * 如果有这个排名，则添加失败，并给出提示
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，是否插入不了
        HeroNode temp = head;
        //标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            //说明到链表的最后了
            if (temp.next == null) {
                break;
            }
            //位置找到，就在temp的后面插入
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                //添加的节点已经存在
                flag = true;
                break;
            }
            //后移动
            temp = temp.next;
        }
        if (flag) {
            System.out.println("节点已经存在");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }




    /**
     * 修改结点信息，根据no编号修改，no不能修改
     * 说明
     * 1.根据newHeroNode的no来修改即可
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;//已经遍历完
            }
            if (temp.no == newHeroNode.no) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.println("没有找到");
        }

    }


    /**
     * 删除节点
     * 1。head不能动，因此我们需要一个temp辅助节点找到需要删除的前一个节点
     * 2.说用我们在比较时，是temp。next.no 和需要删除的节点的no比较
     */
    public void delete(int no) {
        HeroNode temp = head;
        boolean boo = false;
        while (true) {
            if (temp.next == null) {
                //已经到最后
                break;
            }

            if (temp.next.no == no) {
                //找到需要删除的前一个节点
                boo = true;
                break;
            }
            temp = temp.next;
        }

        if (boo) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到这个节点");
        }
    }


    /**
     * 显式链表（遍历）
     */
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因为我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表的最后
            if (temp == null) {
                break;
            }
            //输出结点信息
            System.out.println(temp);
            //将节点后移
            temp = temp.next;
        }
    }


}

/**
 * 定义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.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "no=" + no + ", name=" + name + ", nickname=" + nickname;
    }
}

但链表的反转

package com.algorithm.linkedlist;


/**
 * 单项链表
 * 直接添加到链表尾部
 * 是根据插入顺序而排序，不会根据序号排序
 *
 * @author：XMD
 * @date: 8.8.22
 */
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, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode4);

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        //显式
        singleLinkedList.list();

//        HeroNode newHeroNode4 = new HeroNode(2, "小炉子", "玉观音");
//        singleLinkedList.update(newHeroNode4);
//
//        System.out.println("<<<<<<<<<<<<<<");
//
//        singleLinkedList.list();
//        System.out.println("<<<<<<<<<<<<<<");

//        singleLinkedList.delete(2);
//        singleLinkedList.delete(4);
//        singleLinkedList.list();
//
//        System.out.println("<<<<<<<<<<<<<<");
//        int length = getLength(singleLinkedList.getHead());
//        System.out.println(length);
//
//        System.out.println("<<<<<<<<<<<<<<");
//        HeroNode heroNode = findHeroNodeByIndex(singleLinkedList.getHead(), 6);
//        System.out.println(heroNode);
        System.out.println("<<<<<<<<<<<<<<");
        reversetList(singleLinkedList.getHead());
        singleLinkedList.list();
    }


    /**
     * 方法，获取单链表的节点个数（如果是待头节点的链表，需求不需要统计）
     */
    public static int getLength(HeroNode heroNode){
        int length = 0;
        if (heroNode.next == null){
            //说明为空链表
            return length;
        }

        //这里没有统计头节点
        HeroNode cur = heroNode.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }


    /**
     * 将链表反转
     * @param head
     */
    public static void reversetList(HeroNode head){
        //如果当前链表为空或者只有一个节点，无需反转
        if (head.next == null || head.next.next == null){
             return;
        }
        //定义一个辅助指针，帮助我们遍历原来的俩链表
        HeroNode cur = head.next;
        //指向当前节点cur的下一个节点
        HeroNode next;
        HeroNode  reversetHead = new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reversetHead的最前端
        while(cur != null){
            //先暂时保存当前节点的下一个节点，因为后面需要使用
            next = cur.next;
            //将cur的下一个节点指向新的链表的最前端
            cur.next = reversetHead.next;
            reversetHead.next = cur;
            //cur后移
            cur = next;
        }
        //将head.next指向reversetHead.next，实现单链表的反转
        head.next = reversetHead.next;
    }


    /**
     * 查找单链表中的倒数第K个结点【新浪面试题】
     * 思路
     * 1，编写一个方法，接收head节点，同时接收一个index
     * 2.index表示是倒数第index个结点
     * 3.先把链表从头到尾遍历，得到链表的总长度
     * 4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
     * 5.如果找到，则返回节点，否则返回null
     */

    public static HeroNode findHeroNodeByIndex(HeroNode head,int index){
        if (head.next == null){
            //没有找到
            return null;
        }
        //链表的长度
        int size = getLength(head);
        //如果index等于0，或者index的长度大于链表的长度，就返回null
        if (index <= 0 || index > size){
            return null;
        }
        //定义辅助变量
        HeroNode temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {
    /**
     * 先初始化一个头节点，头节点不要动，不存放具体数据
     */
    private HeroNode head = new HeroNode(0, "", "");
    public HeroNode getHead(){
        return head;
    }

    /**
     * 第一种添加方式
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入指定位置
     * 如果有这个排名，则添加失败，并给出提示
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，是否插入不了
        HeroNode temp = head;
        //标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            //说明到链表的最后了
            if (temp.next == null) {
                break;
            }
            //位置找到，就在temp的后面插入
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                //添加的节点已经存在
                flag = true;
                break;
            }
            //后移动
            temp = temp.next;
        }
        if (flag) {
            System.out.println("节点已经存在");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }




    /**
     * 修改结点信息，根据no编号修改，no不能修改
     * 说明
     * 1.根据newHeroNode的no来修改即可
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;//已经遍历完
            }
            if (temp.no == newHeroNode.no) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.println("没有找到");
        }

    }


    /**
     * 删除节点
     * 1。head不能动，因此我们需要一个temp辅助节点找到需要删除的前一个节点
     * 2.说用我们在比较时，是temp。next.no 和需要删除的节点的no比较
     */
    public void delete(int no) {
        HeroNode temp = head;
        boolean boo = false;
        while (true) {
            if (temp.next == null) {
                //已经到最后
                break;
            }

            if (temp.next.no == no) {
                //找到需要删除的前一个节点
                boo = true;
                break;
            }
            temp = temp.next;
        }

        if (boo) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到这个节点");
        }
    }


    /**
     * 显式链表（遍历）
     */
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因为我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表的最后
            if (temp == null) {
                break;
            }
            //输出结点信息
            System.out.println(temp);
            //将节点后移
            temp = temp.next;
        }
    }


}

/**
 * 定义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.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "no=" + no + ", name=" + name + ", nickname=" + nickname;
    }
}

节点已经存在
no=1, name=宋江, nickname=及时雨
no=2, name=卢俊义, nickname=玉麒麟
no=3, name=吴用, nickname=智多星
no=4, name=林冲, nickname=豹子头
<<<<<<<<<<<<<<
no=4, name=林冲, nickname=豹子头
no=3, name=吴用, nickname=智多星
no=2, name=卢俊义, nickname=玉麒麟
no=1, name=宋江, nickname=及时雨

从尾到头打印单链表

package com.algorithm.linkedlist;


import java.util.Stack;

/**
 * 单项链表
 * 直接添加到链表尾部
 * 是根据插入顺序而排序，不会根据序号排序
 *
 * @author：XMD
 * @date: 8.8.22
 */
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, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode4);

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        //显式
        singleLinkedList.list();

//        HeroNode newHeroNode4 = new HeroNode(2, "小炉子", "玉观音");
//        singleLinkedList.update(newHeroNode4);
//
//        System.out.println("<<<<<<<<<<<<<<");
//
//        singleLinkedList.list();
//        System.out.println("<<<<<<<<<<<<<<");

//        singleLinkedList.delete(2);
//        singleLinkedList.delete(4);
//        singleLinkedList.list();
//
//        System.out.println("<<<<<<<<<<<<<<");
//        int length = getLength(singleLinkedList.getHead());
//        System.out.println(length);
//
//        System.out.println("<<<<<<<<<<<<<<");
//        HeroNode heroNode = findHeroNodeByIndex(singleLinkedList.getHead(), 6);
//        System.out.println(heroNode);
        System.out.println("<<<<<<<<<<<<<<");
//        reversetList(singleLinkedList.getHead());
//        singleLinkedList.list();

        reversetPrint(singleLinkedList.getHead());
    }


    /**
     * 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就能实现逆序打印的效果
     * @param head
     */
    public static void reversetPrint(HeroNode head){
        if (head.next == null){return;}
        Stack<HeroNode> stack= new Stack<>();
        HeroNode cur = head.next;
        //将链表的所有节点压入栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //将栈中的节点打印。pop 出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

    /**
     * 方法，获取单链表的节点个数（如果是待头节点的链表，需求不需要统计）
     */
    public static int getLength(HeroNode heroNode){
        int length = 0;
        if (heroNode.next == null){
            //说明为空链表
            return length;
        }

        //这里没有统计头节点
        HeroNode cur = heroNode.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }


    /**
     * 将链表反转
     * @param head
     */
    public static void reversetList(HeroNode head){
        //如果当前链表为空或者只有一个节点，无需反转
        if (head.next == null || head.next.next == null){
             return;
        }
        //定义一个辅助指针，帮助我们遍历原来的俩链表
        HeroNode cur = head.next;
        //指向当前节点cur的下一个节点
        HeroNode next;
        HeroNode  reversetHead = new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reversetHead的最前端
        while(cur != null){
            //先暂时保存当前节点的下一个节点，因为后面需要使用
            next = cur.next;
            //将cur的下一个节点指向新的链表的最前端
            cur.next = reversetHead.next;
            reversetHead.next = cur;
            //cur后移
            cur = next;
        }
        //将head.next指向reversetHead.next，实现单链表的反转
        head.next = reversetHead.next;
    }


    /**
     * 查找单链表中的倒数第K个结点【新浪面试题】
     * 思路
     * 1，编写一个方法，接收head节点，同时接收一个index
     * 2.index表示是倒数第index个结点
     * 3.先把链表从头到尾遍历，得到链表的总长度
     * 4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
     * 5.如果找到，则返回节点，否则返回null
     */

    public static HeroNode findHeroNodeByIndex(HeroNode head,int index){
        if (head.next == null){
            //没有找到
            return null;
        }
        //链表的长度
        int size = getLength(head);
        //如果index等于0，或者index的长度大于链表的长度，就返回null
        if (index <= 0 || index > size){
            return null;
        }
        //定义辅助变量
        HeroNode temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

}

/**
 * 定义SingleLinkedList管理我们的英雄
 */
class SingleLinkedList {
    /**
     * 先初始化一个头节点，头节点不要动，不存放具体数据
     */
    private HeroNode head = new HeroNode(0, "", "");
    public HeroNode getHead(){
        return head;
    }

    /**
     * 第一种添加方式
     * 思路，当不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后的结点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入指定位置
     * 如果有这个排名，则添加失败，并给出提示
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，是否插入不了
        HeroNode temp = head;
        //标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            //说明到链表的最后了
            if (temp.next == null) {
                break;
            }
            //位置找到，就在temp的后面插入
            if (temp.next.no > heroNode.no) {
                break;
            } else if (temp.next.no == heroNode.no) {
                //添加的节点已经存在
                flag = true;
                break;
            }
            //后移动
            temp = temp.next;
        }
        if (flag) {
            System.out.println("节点已经存在");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }




    /**
     * 修改结点信息，根据no编号修改，no不能修改
     * 说明
     * 1.根据newHeroNode的no来修改即可
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;//已经遍历完
            }
            if (temp.no == newHeroNode.no) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.println("没有找到");
        }

    }


    /**
     * 删除节点
     * 1。head不能动，因此我们需要一个temp辅助节点找到需要删除的前一个节点
     * 2.说用我们在比较时，是temp。next.no 和需要删除的节点的no比较
     */
    public void delete(int no) {
        HeroNode temp = head;
        boolean boo = false;
        while (true) {
            if (temp.next == null) {
                //已经到最后
                break;
            }

            if (temp.next.no == no) {
                //找到需要删除的前一个节点
                boo = true;
                break;
            }
            temp = temp.next;
        }

        if (boo) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到这个节点");
        }
    }


    /**
     * 显式链表（遍历）
     */
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因为我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表的最后
            if (temp == null) {
                break;
            }
            //输出结点信息
            System.out.println(temp);
            //将节点后移
            temp = temp.next;
        }
    }


}

/**
 * 定义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.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "no=" + no + ", name=" + name + ", nickname=" + nickname;
    }
}

打印

no=1, name=宋江, nickname=及时雨
no=2, name=卢俊义, nickname=玉麒麟
no=3, name=吴用, nickname=智多星
no=4, name=林冲, nickname=豹子头
<<<<<<<<<<<<<<
no=4, name=林冲, nickname=豹子头
no=3, name=吴用, nickname=智多星
no=2, name=卢俊义, nickname=玉麒麟
no=1, name=宋江, nickname=及时雨