[数据结构和算法02]约瑟夫环问题看这篇就够了！！！

���来第二期是要更新排序的，但是发现明天学校的算法课实验是有关约瑟夫问题的，这个问题还蛮有意思的，觉得可以加更一期，话不多说，开始！

一.什么是约瑟夫问题

已知n个人(以编号1,2.3..n分别表示)围坐在一张圆桌周围。从编号为K的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到只剩下一个人为止。

解决这个问题的数据结构实际上就是一个单向链表，不过和普通的单向链表不一样，这个单向链表的首尾是相连的，也就是说这是一个环形链表，所以我们要先构建一个环形链表。

二.构建单向环形链表

1.Node类

首先把链表的结点定义出来，这个类有两个属性，和以前的链表一模一样，一个存编号，一个存下一个结点的引用：

package com.jtl.joseph;/** * @description:单向环形链表的每个结点 */public class Node {    private int no;    private Node next;    public Node(int no){        this.no = no;    }    public int getNo() {        return no;    }    public void setNo(int no) {        this.no = no;    }    public Node getNext() {        return next;    }    public void setNext(Node next) {        this.next = next;    }}

没什么好说的，给相应的set、get方法就行了。

2.构建环形链表

然后我们就可以构建环形链表了，在这里我先画个图，解释一下环形链表是长啥样的，方便后面解释分析：

环形链表示意图

所以我们就可以得到怎么构建上面这个环形链表的思路：

1.先new第一个结点，然后定义first指针指向该节点，而且要形成环形结构（也就是说即使只有一个结点，它的next不能为空，也应该为first）

2.后面每次创建一个新的结点，就把该结点加入到环形链表中就可以了，这里加入的时候要用一个辅助指针来记录first的位置，因为咱们的first是不能随便改变的

具体实现：

package com.jtl.joseph;/** * @description:代表单向环形链表 */public class CircleLinkedList {    private Node first = null;//头结点;        //addNode方法，构建一个长度为nums的环形链表    public void addNode(int nums){        if(nums  
最终测试结果，应该是没问题的：
 
三.总结 
 
这个问题的难点在于如何构建这个环形链表，其他的其实没什么，主要就是指针的移动还有指向问题需要注意，要记住什么不能随便变，如果想要借助这个不能变的东西做一些事情，就得用到一个临时变量或者辅助变量temp去解决;