单链表的节点

节点非常简单,就一个必要的id和下一个指向的next 还有一个简单的属性name

public class HeroNode3 {
    int id;
    String name;
    HeroNode3 next;

    public HeroNode3(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode3{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
复制代码

环形单链表创建

分析:

环形单链表其实和环形队列一样,都是将最后一个元素指向第一个元素,然后就完成了环状

总结:

记录第一个元素,然后每次添加的时候都指向第一个元素即可

来看看代码:

public class AnnularLinkedList {
    //
    private HeroNode3 head;

 /**
     * 创建元素
     *
     * @param sum 需要创建的个数
     */
    public void createHeroNode(int sum) {
        if (sum < 1) {
            System.out.println("请正确输入创建个数");
            return;
        }

        HeroNode3 temp = null;

        for (int i = 1; i <= sum; i++) {
            HeroNode3 node3 = new HeroNode3(i, "张三" + i);

            if (i == 1) {
                //记录第一个位置
                head = node3;
                //辅助变量，记录第一个位置
                temp = node3;
                //第一个元素指向自己,构建成环形
                head.next = head;
            }

            //指向新的元素
            temp.next = node3;

            //新的元素指向第一个节点
            node3.next = head;

            //temp后移
            temp = temp.next;
        }
    }
}
复制代码

测试:

        AnnularLinkedList linkedList = new AnnularLinkedList();

        linkedList.createHeroNode(5);
        
        //这是一个非常笨的办法,一直.next 超出5个部分看看会不会下标越界
        System.out.println("测试的值为:"+linkedList.getHead().next.next.next.next.next.next);
复制代码

最终结果为:

测试的值为:HeroNode3{id=2, name='张三2'}
复制代码

看不懂没关系,图解了解一下:

环形单链表创建.png

环形单链表输出

先来看代码:

     /**
     * 输出链表所有数据
     */
    public void show() {
        if (head == null) {
            System.out.println("链表为null,不能打印");
        }
        HeroNode3 temp = head;

        while (temp.next != null) {
            System.out.println("show:" + temp);

            //当最后一个元素 = 第一个元素时,表示链表当前在最后一个元素,停止循环
            if (temp.next == head) {
                break;
            }

            //temp后移
            temp = temp.next;
        }
    }
复制代码

分析:

当第一个节点等于最后一个节点的时候,那么证明环形链表完成!

测试:

  AnnularLinkedList linkedList = new AnnularLinkedList();

  linkedList.createHeroNode(5);

  linkedList.show();
复制代码

运行结果为:

show:HeroNode3{id=1, name='张三1'}
show:HeroNode3{id=2, name='张三2'}
show:HeroNode3{id=3, name='张三3'}
show:HeroNode3{id=4, name='张三4'}
show:HeroNode3{id=5, name='张三5'}
复制代码

约瑟夫问题

什么是约瑟夫问题:

约瑟夫问题就和丢手绢一样,一群孩子围绕着一圈,然后从某一个孩子开始,过几个孩子吧手绢丢下,然后当前孩子就‘出圈’了

百度百科

假设现在有5个孩子丢手绢,从第3个孩子开始丢,丢2下孩子出圈

sum = 5
start = 3
count = 2

图解:

最终结果为:

从第几个孩子开始报数分析:

(拿孩子3开始数数来举例(默认从第0个孩子数数)):

help一直跟随在head后面,后面出圈使用!

图解:

报数几下分析:

(拿孩子3开始数数,报数2下来举例):

报数几下分析和从第几个孩子开始报数思路是一样的,都是将head和help向后移:

图解:

数2下出圈,孩子3需要自身数1下,孩子4数一下,所以就移动到了孩子4的位置

出圈分析:

首先看看代码是怎么出圈的吧:

(拿孩子4出圈来举例)

需要一个辅助节点,一直指向head节点的后一个位置

第一步: head = head.next

第二步: help.next = head

此时孩子4就出圈了,最后孩子4就会被JVM垃圾回收机制回收

在来看看代码吧:

/**
     * @param start  从元素几开始数
     * @param number 每数几下出圈
     */
    public void count(int start, int number) {
        
        //获取链表长度
        int sum = size();
        System.out.println("sum为:" + start + "\t" + number + "\t" + sum);

        //start < 1  不能从 < 1 开始的数 数
        //sum < start  链表总数不能 < 开始的位置
        if (start < 1 || sum < start) {
            System.out.println("请正确输入");
            return;
        }

        HeroNode3 help = head;

        //将 help 移动到 head 后面
        while (help.next != head) {
            help = help.next;
        }

        //从第start位置开始循环
        for (int i = 0; i < start - 1; i++) {
            head = head.next;
            help = help.next;
        }

        //如果heap != head 那么就继续循环
        //当help == head 时，则退出循环
        while (help != head) {

            //每number下出圈
            for (int i = 0; i < number - 1; i++) {
                head = head.next;
                help = help.next;
            }
            //此时head则为要出圈的元素
            System.out.println("要出圈的勇士id为:" + head.id);

            //出圈操作
            head = head.next;
            help.next = head;
        }

        //最终help = head  那么help/head就是最后一个在圈中的元素
        System.out.println("留在圈中的勇士id为:" + help.id);
    }
复制代码

测试:

AnnularLinkedList linkedList = new AnnularLinkedList();

        linkedList.createHeroNode(5);

        System.out.println("测试的值为:"+linkedList.getHead().next.next.next.next.next.next);

        linkedList.show();

        linkedList.count(3, 2);
复制代码

运行结果为:

测试的值为:HeroNode3{id=2, name='张三2'}
show:HeroNode3{id=1, name='张三1'}
show:HeroNode3{id=2, name='张三2'}
show:HeroNode3{id=3, name='张三3'}
show:HeroNode3{id=4, name='张三4'}
show:HeroNode3{id=5, name='张三5'}
sum为:3	2	5
要出圈的勇士id为:4
要出圈的勇士id为:1
要出圈的勇士id为:3
要出圈的勇士id为:2
留在圈中的勇士id为:5
复制代码