4.环形链表和约瑟夫问题

问题引出：

单行环形链表

代码实现：

1.定义一个Childtren实体
    class Children {
        //编号
        private int no;
        //下一个
        private Children next;
        //对应的get/set方法，和no的构造器
   }
   
2.单项唤醒链表管理类
    class CirleSingleLinkedlist {
        //第一个元素不能动
        Children first = null;
        //定义一个辅助指针代表当前元素
        Children current = null;

        /**
         * 添加多少元素
         *
         * @param num 小孩个数
         */
        public void addChild(int num) {
            if (num < 1) {
                System.out.println("请正确输入元素个数！");
                return;
            }
            for (int i = 1; i <= num; i++) {
                Children child = new Children(i);
                //如果只有一个自己成一个环
                /*
                  心得：
                      1.首先需要定义一个first节点，这个节点不能动，因为在最后一个节点.next=first节点，并且遍历需要从该节点出发  
                      2.当初考虑从num==1和其他分为两种情况进行，但是这种后果是，如果num等于多个时，首节点不好处理，所以下述是最好的处理办法
                  */
                  //每次循环都是一个环
                if (i == 1) {
                    first = child;
                    first.setNext(first);
                    current = first;
                } else {
                    current.setNext(child);
                    child.setNext(first);
                    current = child;
                }
            }
        }
        //遍历该单项环形链表
        public void showChild() {
            if (first == null) {
                System.out.println("列表为空！");
                return;
            }
            current = first;
            while (current != null) {
                System.out.println("编号：" + current.getNo());
                if (current.getNext() == first) {
                    break;
                }
                current = current.getNext();
            }
        }
    }

测试：
    public class JosePfu {
        public static void main(String[] args) {
            CirleSingleLinkedlist cirleSingleLinkedlist = new CirleSingleLinkedlist();
            cirleSingleLinkedlist.addChild(20);
            cirleSingleLinkedlist.showChild();
        }
    }
    
输出：
编号：1
编号：2
编号：3
编号：4
编号：5
编号：6
编号：7
编号：8
编号：9
编号：10
编号：11
编号：12
编号：13
编号：14
编号：15
编号：16
编号：17
编号：18
编号：19
编号：20
    

约瑟夫出圈

出圈逻辑图：

/**
     * 小孩出圈顺序，总共有nums个元素，从startno处开始数countNum次，该元素出圈，再从下一个元素继续数countNum次，再出圈，输出出圈顺序
     *
     * @param startNo  开始序号
     * @param countNum 数几下
     * @param nums     总共有几个元素
     */
    public void countChild(int startNo, int countNum, int nums) {
        if (startNo < 1 || first == null || startNo > nums) {
            System.out.println("输入错误，重新输入！");
        }
        /*
            1.定义一个辅助节点，指向需要出圈元素的上一个元素，出圈就是删除，单项链表没哟获取上一个元素的方法，只有获取下一个元素的方法
            2.删除元素是通过：如果a是删除元素，a的上一个元素.next=a的下一个元素，去删除a元素
         */

        Children helper = first;
        //所以该元素开始需要指向first的上一个元素
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        //1.先将first移动到需要开始的位置
        for (int i = 1; i < startNo; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //2.开始循环出圈
        while (true) {
            //当开始元素==辅助元素时，队列里只有一个元素了，退出
            if (first == helper) {
                break;
            }
            for (int i = 1; i < countNum; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //3.经过上述循环，first指向的就是出圈的那个元素，current指向的是出圈的上一个元素
            System.out.println("出圈：" + first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("剩余元素为："+first.getNo());
    }
}

总结:

 1.因为是单项链表没有获取上一个元素的方法，只有getnext，所以需要一个辅助元素helper指向要出圈的上一个元素

  2.移动first位置，使first指向需要出圈的元素，helper指向出圈元素的上一个元素

     3.开始需要将helper移动到最后一个元素，即fist的上一个元素，预防删除第一个元素

  4.当helper和first相等，即队列中再有一个元素，其他已经出圈完毕

测试：
    public class JosePfu {
        public static void main(String[] args) {
            CirleSingleLinkedlist cirleSingleLinkedlist = new CirleSingleLinkedlist();
            cirleSingleLinkedlist.addChild(5);
            cirleSingleLinkedlist.showChild();
            System.out.println("约瑟夫出圈----------------");
            //从第一个位置开始，数2下的那个元素出圈
            cirleSingleLinkedlist.countChild(1, 2, 5);
        }
    }
    
输出：
    出圈：2
    出圈：4
    出圈：1
    出圈：5
    剩余元素为：3
    
和预期一致！


测试2：这种不好确认的话，这种
    从第一个元素开始，数1下的元素出圈，即顺序出圈，预期为1,2,3,4,5
    cirleSingleLinkedlist.countChild(1, 1, 5);

输出：复合预期
    编号：1
    编号：2
    编号：3
    编号：4
    编号：5
    约瑟夫出圈----------------
    出圈：1
    出圈：2
    出圈：3
    出圈：4
    剩余元素为：5

原文地址：http://www.cnblogs.com/wmd-l/p/16905913.html