[数据结构与算法] 邂逅链表

package ah.sz.tp.algorithm1;

/**
 * 单链表实现水浒英雄榜
 * 1. 创建节点模型, 规定排行, 名字, 外号, 下一个节点; 重写构造,toString()
 * 2. 创建链表实体, 创建头节点属性, 创建增删改查的方法
 * 3. 在main()中进行操作
 *
 * @author TimePause
 * @create 2020-01-09 16:52
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        Node hero1 = new Node(1, "宋江", "及时雨");
        Node hero2 = new Node(2, "卢俊义", "玉麒麟");
        Node hero3 = new Node(3, "吴用", "智多星");
        Node hero4 = new Node(4, "林冲", "豹子头");
        // 将这些节点加入链表中
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero4);
        // 显示链表数据
        singleLinkedList.showLinkedList();


    }
}

class Node{
    public int no;
    public String name;
    public String nickName;
    public Node next;

    public Node(int no, String name, String nickName) {//去掉next,因为它需要在我们添加时手动指定
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {//需要将next的输出去掉
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

class SingleLinkedList{
    // 初始化头节点
    private Node head = new Node(0, "", "");

    /**
     * 添加节点到单链表(不考虑顺序)
     * 1. 找到当前链表的最后一个节点
     * 2. 将这个节点的next 指向新的节点
     */
    public void add(Node heroNode){
        //因为head节点不能移动, 因此我们需要辅助变量temp来辅助遍历
        Node temp=head;
        // 定义循环结束的变量
        boolean flag = true;
        while (flag){
            // 如果当前节点next为null,说明是链表的最后
            if (temp.next==null){
                // 这个节点的next 指向新的节点
                temp.next = heroNode;
                flag = false;
            }
            // 如果执行到这里, 说明没有找到最后
            temp = temp.next;

        }
    }

    /**
     * 显示整个链表
     */
    public void showLinkedList(){
        // 判断链表是否为空
        if (head.next==null){
            System.out.println("当前列表为空,请手动添加数据~~~");
            return;
        }
        // 不为空, 则遍历每个节点, 借助辅助变量temp
        Node temp = head.next;
        while (true){
            // 如果是最后
            if (temp==null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            // 一定要将temp后移
            temp = temp.next;
        }

    }

}

 /**
     * 添加英雄时, 根据排名将英雄添加到指定的位置
     * 如果排名已存在,则显示已存在
     */
    public void addByOrder(Node heroNode) {
        //因为头节点不能动, 我们需要使用辅助(相当于c中的指针)变量,来帮助找到添加的位置
        //因为是单链表, 因为我们找到temp是位于添加位置前的一个节点, 否则插入不了
        Node temp = head;//这里的temp实际上指待插入节点的前一个节点
        // 用于标志插入的编号是否存在
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//说明位于最后
                break;
            }
            if (temp.next.no > heroNode.no) {//说明这个就是应该插入的位置
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //通过flag判断插入的元素是否存在
        if (flag) {//已存在
            System.out.printf("您要保存的英雄 %d 已经存在,不能够加入\n", heroNode.no);
        } else {//说明不存在,执行插入
            //将插入节点的指针指向下一个节点
            heroNode.next = temp.next;
            //将要插入节点的上一个节点的指针指向要插入的节点
            //temp.next在左边: 表示要插入节点的上一个节点的指针, 在右边表示要插入节点的下一个节点!!!
            temp.next = heroNode;
        }
    }

public static void main(String[] args) {
        Node hero1 = new Node(1, "宋江", "及时雨");
        Node hero2 = new Node(2, "卢俊义", "玉麒麟");
        Node hero3 = new Node(3, "吴用", "智多星");
        Node hero4 = new Node(4, "林冲", "豹子头");
        // 将这些节点加入链表中
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
		// 显示链表数据
        singleLinkedList.showLinkedList();


    }
}

  /**
     * 修改英雄属性
     */
    public void update(Node newHeroNode) {
        // 首先需要判断是否为空
        if (head.next == null) {
            System.out.println("队列为空");
        }
        // 判断是需要修改的节点否存在
        boolean flag = false;
        //因为是单链表, 因为我们找到temp是位于添加位置前的一个节点
        Node temp = head.next;
        while (true) {
            if (temp == null) {//我们首先会设想为空值的情况,说明一件到链表末尾
                break;//遍历完未找到
            }
            if (temp.no == newHeroNode.no) {//找到
                flag = true;
                break;
            }
            //让temp不停的往下走, 即令temp不断的指向下一个节点
            temp = temp.next;
        }
        if (flag) {
            // 修改其姓名和外号,编号不可修改
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {
            System.out.printf("您修改的编号为 %d 的英雄不存在!!!", newHeroNode.no);
        }

    }

 		singleLinkedList.update(new Node(4,"chy","时间静止"));
         // 显示链表数据
        singleLinkedList.showLinkedList();

 /**
     * 根据英雄编号删除节点
     */
    public void del(int delHerono) {
        // 头节点不能动, 需要辅助变量
        Node temp = head;
        // 标记要删除的节点是否存在
        boolean flag = false;
        while (true) {
            if (temp.next == null) {//说明已到链表的末尾
                break;
            }
            if (temp.next.no == delHerono) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            //将当前节点的下个节点指针指向下下个节点,相当于是删除了下一个节点(依靠GC)
            temp.next = temp.next.next;
        }else {
            System.out.println("要删除的节点不存在");
        }
    }

 	    singleLinkedList.del(1);
        singleLinkedList.del(4);
        singleLinkedList.del(2);
        singleLinkedList.del(3);
        // 显示链表数据
        singleLinkedList.showLinkedList();

class Node {
    public int no;
    public String name;
    public String nickName;
    public Node next;

    public Node(int no, String name, String nickName) {//去掉next,因为它需要在我们添加时手动指定
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {//需要将next的输出去掉
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

class SingleLinkedList {
    // 初始化头节点
    public Node head = new Node(0, "", "");

	 // 获取头节点
	    public Node getHead() {
	        return head;
	    }
}

/**
     * 面试题1: 获取单链表节点的个数(不统计头节点)
     * 但是要通过头节点
     */
    public static int getLinkedListLength(Node head) {
        if (head.next == null) {//说明当前节点长度为0
            return 0;
        }
        //定义辅助变量
        Node temp = head.next;
        int length = 0;
        while (temp != null) {//判断该变量是否为空
            length++;
            temp = temp.next;//执行循环
        }
        return length;
    }

 System.out.println(getLinkedListLength(singleLinkedList.getHead()));
   // 显示链表数据
   singleLinkedList.showLinkedList();

    /**
     * 面试题2: 查找单链表中倒数第k(index)个节点(1的基础上进行)
     * 1. 编写一个方法, 接收head, 接收index表示倒数第k个节点
     * 2. 遍历链表, 得到总长度 size=getLinkedListLength()
     * 3. 得到size会后. 重新遍历链表, 便利到 (size-index)个
     * 4. 如果找到则返回该节点, 找不到则提示空
     */
    public static Node findLastIndexOfLinkedList(Node head, int index) {
        if (head.next == null) {
            return null;
        }
        //获取总长度
        int size = getLinkedListLength(head);
        // 对输入的index进行判断
        if (index <= 0 || index > size) {
            System.out.println("设置的索引有误,请重新设置");
        }
        //辅助变量, 不包括头节点
        Node temp = head.next;
        // 重新遍历链表
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;//第size-index即为倒数第index节点,对应temp.next的那个节点
        }
        return temp;
    }

// 显示链表数据
        singleLinkedList.showLinkedList();
        //倒数第k个节点为
        System.out.println("倒数第k个节点为");
        Node node = findLastIndexOfLinkedList(singleLinkedList.getHead(), 1);
        System.out.println(node);

 /**
     * 面试题3:实现单链表反转
     * 1. 定义一个节点,代表反转节点 reverseHead=new HeroNode()
     * 2. 从头到尾遍历原来的链表, 每遍历一个节点, 就将其取出, 放在新链表reverseHead的最前面
     * 3. 原来的链表 head.next = reverseHead.next '=':指针的指向功能
     */
    public static void reverseLinkedList(Node head){
        // 如果当前列表为空, 或者只有一个节点, 无需反转, 直接返回
        if (head.next==null || head.next.next==null){
            return;
        }
        // 定义一个辅助变量/指针, 遍历原来的链表
        Node cur = head.next;
        // 定义当前节点[cur]的下一个节点
        Node next= null;
        // 新链表的头结点
        Node reverseHead = new Node(0, "", "");
        // 遍历原来的列表, 每遍历一个节点, 就将其取出, 放在新链表reverseHead的第一个节点
        // 仔细思考
        while (cur!=null){
            // 1.保存当前节点的下一个节点
            next = cur.next;
            // 2.将cur的指针指向新的链表头结点后的第一个节点
            cur.next = reverseHead.next;
            // 3.将新链表的头结点指针指向cur
            reverseHead.next = cur;
            // 4.相当于cur后移
            cur = next;
        }
        // 将原来头结点指针指向新链表头结点后第一个节点
        head.next = reverseHead.next;

    }

 // 显示链表数据
        singleLinkedList.showLinkedList();
        System.out.println("实现链表的反转");
        reverseLinkedList(singleLinkedList.getHead());
        // 显示链表数据
        singleLinkedList.showLinkedList();

/**
 * 测试栈的使用
 *
 * @author TimePause
 * @create 2020-01-10 16:38
 */
public class TestStack {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        //入栈
        stack.add("man1");
        stack.add("man2");
        stack.add("man3");
        //出栈
        while (stack.size()>0){
            System.out.println(stack.pop());
        }

    }
}

 /**
     * 面试题4: 实现单链表的逆序打印
     * 利用栈(先进后出), 将各个节点压入栈中, 然后再弹出打印
     */
    public static void reversePrint(Node head){
        // 判断链表是否为空
        if (head.next==null){
            return;
        }
        // 创建一个辅助变量/指针
        Node cur = head.next;
        // 创建一个栈
        Stack<Node> nodeStack = new Stack<>();
        while (cur!=null){
            nodeStack.add(cur);
            cur = cur.next;
        }
        while (nodeStack.size()>0){
            System.out.println(nodeStack.pop());
        }

    }

  // 显示链表数据
        singleLinkedList.showLinkedList();
        System.out.println("逆序打印链表. 通过栈的方式");
        reversePrint(singleLinkedList.getHead());

package ah.sz.tp.algorithm1;

/**
 * 使用双链表完成水浒英雄排行榜
 *
 * @author TimePause
 * @create 2020-01-10 20:37
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        // 创建并添加四条数据
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        // 创建双链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
        // 执行修改操作
        //doubleLinkedList.undate(new HeroNode(4,"chy","时间静止不是简史"));
        //执行删除操作
        doubleLinkedList.delete(4);
        doubleLinkedList.showDoubleLinkedList();
        // 显示数据


    }
}

class DoubleLinkedList{
    //双链表的头节点
    public HeroNode head = new HeroNode(0, "", "");


    /**
     * 双向链表的删除(无序)
     * 核心代码
     * temp.pre.next=temp.next
     * temp.next.pre=temp.pre
     * 解析
     * temp的pre(上一个)节点的next指针指向temp的下一个节点=>相当于上面逻辑图中的那条红线,绕过了temp=>建立了next关系
     * temp的next(下一个节点)的next指针指向temp的上一个节点=>相当于上面的逻辑图中的红线下面的蓝色线,也是绕过了temp=>建立了pre关系
     * 但是,在执行temp.next.pre=temp.pre需要注意
     * 如果需要被删除的元素temp位于末尾,则temp.next.pre=null,会报空指针异常
     */

    public void delete(int no){
        //判断该双链表是否为空
        if (head.next==null){
            System.out.println("该链表长度为空");
        }

        // 创建辅助指针/变量, 是head的下一个节点, 单链表中这里是head节点
        // 是因为单链表删除时, 需要找到被删除节点的上一个节点,然后令其指向被删除节点下一个节点, 而双链表可以自动删除
        HeroNode temp = head.next;
        // 创建布尔变量表示待删除节点是否找到
        boolean flag = false;
        while (true){
            if (temp==null){//遍历到最后
                break;
            }
            if (temp.no==no){
                flag = true;
                break;
            }
            //指针后移
            temp = temp.next;
        }
        //判断是否找到
        if (flag){
             //temp的pre(上一个)节点的next指针指向temp的下一个节点=>相当于上面逻辑图中的那条红线,绕过了temp=>建立了next关系
            temp.pre.next=temp.next;
             //temp的next(下一个节点)的next指针指向temp的上一个节点=>相当于上面的逻辑图中的红线下面的蓝色线,也是绕过了temp=>建立了pre关系
            // 如果需要被删除的元素temp位于末尾,则temp.next.pre=null,会报空指针异常,需要判空
            if (temp.next!=null){
                temp.next.pre = temp.pre;
            }

        }else {
            System.out.printf("要删除排行%d的英雄不存在",no);
        }

    }


    /**
     * 双向链表的修改,根据no(和单向链表一样,知识节点类型发生了变化)
     */
    public void undate(HeroNode updateHeroNode){
        //判断第一个节点是否为空
        if (head.next==null){
            System.out.println("该链表长度为空");
            return;
        }
        //定义辅助指针/变量
        HeroNode temp = head.next;
        //定义该节点是否找到
        boolean flag = false;
        while (true){
            if (temp==null){
                break;
            }
            if (temp.no==updateHeroNode.no){//编号相等说明找到
                flag=true;
                break;
            }
            //不断移动指针
            temp = temp.next;
        }
        // 根据是否找到节点执行相关逻辑
        if (flag){
            temp.name = updateHeroNode.name;
            temp.nickName = updateHeroNode.nickName;
        }else {
            System.out.printf("没有找到排行%d的英雄,不能修改",updateHeroNode.no);
        }

    }

    /**
     * 双向链表的添加
     * 相较于单向链表多了两行代码
     * temp.next=newHeroNode
     * newHeroNode.pre=temp
     */
    public void add(HeroNode newHeroNode){
        //需要辅助变量, 而且因为是添加(可能会从第一个开始添加),辅助变量首先要位于head,而不是head.next
        //如果head.next位于=左边, 说明head的next指针, 如果位于=右边这说明是head的后面一个元素
        HeroNode temp = head;
        while (temp.next!=null){
            temp = temp.next;
        }
        // 如果为空,说明到达双链表尾部
        // 在两个节点之间建立双链表关系
        temp.next = newHeroNode;
        newHeroNode.pre = temp;
    }

    /**
     * 双向链表的遍历
     */
    public void showDoubleLinkedList(){
        // 判断链表的第一个节点是否为空
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        //定义辅助指针/变量
        HeroNode temp = head.next;
        while (temp!=null){
            System.out.println(temp.toString());
            temp = temp.next;
        }

    }



}


class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode pre; //前一个节点
    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 "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

   // 创建并添加四条数据
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        // 创建双链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
        doubleLinkedList.showDoubleLinkedList();

 /**
     * 双链表的添加(画图,结合图去理解!!!)
     */
    public void addByOrder(HeroNode newHeroNode) {
        // 添加不需要判空
        // 创建一个辅助变量/指针
        HeroNode temp = head;
        // 创建一个布尔变量,表示待插入是否存在
        while (true) {
            if (temp.next == null) {//到达链表最后
                //如果插入元素在链表最后, 只需要将temp的next指向新节点,新节点的pre指向temp
                temp.next = newHeroNode;
                newHeroNode.pre = temp;
                break;
            }
            if (temp.next.no > newHeroNode.no) {//找到插入点的位置
                /**
                 * 如果在链表中间找到插入点(temp则位于插入点前,temp.next位于插入点后)
                 * 1.需要创建一个变量nextnode存放插入点的下一个节点temp.next
                 * 2.插入点的pre指向temp,  temp的next指向插入点
                 * 3.nextnode的pre指向插入点, 插入点的下一个节点指向nextnode
                 */
                HeroNode nextnode = temp.next;
                newHeroNode.pre = temp;
                temp.next = newHeroNode;
                newHeroNode.next = nextnode;
                nextnode.pre = newHeroNode;
                break;
            }
            if (temp.next.no == newHeroNode.no) {//找到插入点
                System.out.println("要插入的节点已经存在");
                break;
            }
            //指针后移
            temp = temp.next;
        }
    }

   doubleLinkedList.addByOrder(hero1);
        doubleLinkedList.addByOrder(hero4);
        doubleLinkedList.addByOrder(hero2);
        doubleLinkedList.addByOrder(hero3);
        // 显示数据
        doubleLinkedList.showDoubleLinkedList();

package ah.sz.tp.algorithm1;

/**
 * 单向循环链表学习
 *
 * @author TimePause
 * @create 2020-01-11 20:30
 */
public class SingleCircleLinkedListDemo {
    public static void main(String[] args) {
        // SingleCircleLinkedList singleCircleLinkedList = new SingleCircleLinkedList();
        SingleCircleLinkedListDemo demo = new SingleCircleLinkedListDemo();
        SingleCircleLinkedList list = demo.new SingleCircleLinkedList();
        list.add(5);
        list.showSingleCircleLinkedList();

    }

    /**
     * 创建单向循环链表类
     */
      class SingleCircleLinkedList{
        // 创建第一个节点
        private Boy first=null;
        // 创建临时指针/变量
        private Boy curBoy=null;

        /**
         * 添加方法
         * @param num 添加几个节点
         */
        public void add(int num){
            // 对参数进行校验
            if (num<1){
                System.out.println("添加节点个数有误,请重新添加~~~");
                return;
            }

            //使用for循环来创建我们的环形链表
            for (int i=1;i<=num;i++){
                //创建下一个节点/子节点
                Boy boy=new Boy(i);
                // 如果添加一个节点
                if (i==1){
                    //1.将第一个节点boy作为first(相当于其他链表中的头节点)
                    first=boy;
                    //2.将boy下一个节点指向first(形成环)
                    boy.next = first;//也可以写成 boy.setNext(first); 同理,下面都可以
                    //3. 将指针移动到first(头节点)
                    curBoy = first;
                }else {
                    // 如果添加1个以上节点
                    //1. 将辅助变量指向下一个节点boy 2.将boy指向第一个节点(形成环) 3.一阵移动到一下个节点
                    curBoy.next = boy;
                    boy.next = first;
                    curBoy = boy;
                }
            }

        }

        /**
         * 遍历当前的单向循环链表
         */
        public void showSingleCircleLinkedList(){
            // 判断链表是否非空
            if (first==null){
                System.out.println("当前循环链表为空, 无法遍历哦~~~");
                return;
            }
            // 调用辅助指针完成遍历
            curBoy = first;
            while (true){
                System.out.printf("孩子节点的编号%d \n",curBoy.no);
                if (curBoy.next==first){
                    break;
                }
                curBoy = curBoy.next;
            }

        }

    }



    /**
     * 创建Boy类,用于存放节点信息
     */
    class Boy{
        private int no;//编号
        private Boy next;//代表指向下一个节点

        //带参构造
        public Boy(int no){
            this.no=no;
        }

        public int getNo() {
            return no;
        }

        public Boy getNext() {
            return next;
        }

        public void setNo(int no) {
            this.no = no;
        }

        public void setNext(Boy next) {
            this.next = next;
        }
    }
}

 /**
         * 根据用户输入, 计算小孩出圈的顺序
         *
         * @param startNo  表示从第几个小孩开始数数
         * @param countNum 表示数几下
         * @param nums     表示圈中最初有多少个小孩
         */
        public void countBoy(int startNo, int countNum, int nums) {
            // 1.对参数进行校验
            if (startNo < 1 || countNum > nums || startNo > nums) {
                System.out.println("参数设置有误,请重新设置!!!");
            }
            //创建辅助指针, 帮助小孩节点出圈(循环链表)
            Boy helper = first;
            //2. 让辅助变量helper首先指向这个圈的最后一个节点
            while (true) {
                if (helper.getNext() == first) {
                    break;
                }
                // 指针后移
                helper = helper.getNext(); //or helper.next
            }
            //3. 小孩报数前,先让first和helper移动k-1(startNo-1)次=>从指定地方报数
            for (int i = 0; i < startNo - 1; i++) {
                //同时移动first和helper指针
                first = first.getNext();
                helper = helper.getNext();
            }
            //4.小孩报数时, 让first和helper的指针同时移动m-1(countMun-1),然后出圈
            while (true) {
                if (helper == first) {//说明圈中只剩下一个元素
                    break;
                }
                // 让first和helper的指针同时移动m-1(countMun-1)
                for (int j = 0; j < countNum - 1; j++) {
                    first = first.getNext();
                    helper = helper.getNext();
                }
                //这时first要指向的节点, 就是小孩要出圈的节点
                System.out.printf("小孩节点%d 要出圈\n", first.getNo());
                //5. 将first指向的小孩节点出圈
                //思路:结合图知,首先将first移动到要出圈的节点的下一个节点后,让辅助指针去指向下一个节点,这样要出圈的节点就会被GC
                first = first.getNext();
                helper.setNext(first);
            }
            System.out.printf("最后留在圈中的小孩的编号为%d \n", first.no);

        }

    SingleCircleLinkedListDemo demo = new SingleCircleLinkedListDemo();
        // 创建了内部类, 所以使用这种方式创建内部类对象
        SingleCircleLinkedList list = demo.new SingleCircleLinkedList();
        // 调用添加方法
        list.add(5);
        // 调用遍历显示方法
        list.countBoy(1, 2, 5);