Question

• 将单链表中终端结点的指针端自空指针改为指向头结点，就使整个单链表形成一 个环，这种头尾:相接的单链表称为单循环链表，简称循环链表。

循坏列表的生活情境

• 比出 ,你是一业务员，家在上海。儒要经常出差，行程就是上海到北京一路上的 城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留 后，再乘飞机返回上海，以后，每隔一段时间，你基本还要按照这样的行程开展业务

• 有一次你先到南京开会，接下来要对以上的城市走一遍。此时有人对你说，不行，你得从上海开始，因为上海是第一站。 你会对这人说什么?神经病。哪有这么傻 的，直接回上海根本没有必要，你可以从南京开始，下一站蚌埠，直到北京，之后再 考虑走完上海及苏南的几个城市。显然这表示你是从当中一结点开始遍历整个链裴 , 这都是原来的单链表结构解决不了的问题。

循环链袭和单链表的主要差异

• 循环链袭和单链表的主要差异就在于循环的判断条件土，原沫是判断 p->next(指针域)
  是否为空，现在则是 p-> next 不等于头结点，则循环未结束。
• 在单链表中，我们有了头结点时，我们可以用 0(1) 的时间访问第一个结点，但对于要访问到最后一个结点，却需要 O(n) 时间，因为我们需要将单链表全部扫描一编。
• 循环链表的尾指针方式就用 0(1) 的时间访问到尾部元素

代码实现

public class CycleLinkList {

    Node head; // 头指针
    Node current;// 当前结点对象
    int size;// 结点个数

    public CycleLinkList() {
        // 初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
        this.head = current = new Node(null);
        this.size = 0;// 单向链表，初始长度为零。
        this.head.next = this.head; //最后一个元素指针域指向头结点
    }

    //使用当前结点对象 定位到要操作结点的前一个结点。
    public void index(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数错误！");
        }
        // 说明在头结点之后操作。
        if (index == -1){
            // 第一个数据元素结点的下标是 0，那么头结点的下标自然就是-1
            return;
        }
        current = head.next;
        int temp=0;	 	//临时变量 用户循坏判断当前节点是否到达
        while (current!=head && temp<index){
            //循环找到插入节点的前一个节点
            current=current.next;
            temp++;
        }
    }


    /**
     * 删除思路：
     *
     * 1。定位到当前要删除的下标的对像的前一个节点
     * 2. 通过改变当前删除对象前一个节点的指针域。》指向当前要删除对象的指针域指向的下一个节点。
     * @param index
     * @throws Exception
     */
    public void delete(int index) throws Exception {
        // 判断链表是否为空
        if (isEmpty()) {
            throw new Exception("链表为空，无法删除！");
        }
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);// 定位到要操作结点的前一个结点对象。
        current.setNext(current.next.next);
        size--;
    }

    /**
     * 获取思路：
     * 		从头节点开始遍历。用临时变量 temp 记录遍历的次数。一直遍历等于 index 就不会再行循坏，直接取出当前下标的节点
     * @param index
     * @return
     * @throws Exception
     */
    public Object get(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数非法！");
        }
        index(index);
        return current.getElement();
    }

    /**
     * 指定位置插入节点
     * @param index
     * @param obj
     * @throws Exception
     */
    public void insert(int index, Object obj) throws Exception {
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj,current.next));
        size++;

    }

    /**
     * 未指定下标末尾插入
     * @param obj
     * @throws Exception
     */
    public void insert(Object obj) throws Exception {
        /**
         * 1.判断当前节点指向一下节点的指针域是否为空
         * 如果指针域为空 说明是此节点是末尾节点
         * 直接在尾部修改默认节点的指针域执指向新增的节点，并把新增的节点的指针域指向 null
         */
        while (current.next!=null){
            //循环判断当前节点指针域是否有下一个节点
            current=current.next;
        }
        current.setNext(new Node(obj, current.next));
        size++;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return this.size;
    }


}

public class Node {
	Object element; // 数据域
	Node next; // 指针域

	// 头结点的构造方法
	public Node(Node nextval) {
		this.next = nextval;
	}

	// 非头结点的构造方法
	public Node(Object obj, Node nextval) {
		this.element = obj;
		this.next = nextval;
	}

	// 获得当前结点的指针域
	public Node getNext() {
		return this.next;
	}

	// 获得当前结点数据域的值
	public Object getElement() {
		return this.element;
	}

	// 设置当前结点的指针域
	public void setNext(Node nextval) {
		this.next = nextval;
	}

	// 设置当前结点数据域的值
	public void setElement(Object obj) {
		this.element = obj;
	}

	public String toString() {
		return this.element.toString();
	}


}

约瑟夫环

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号 1，2，3...n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从 0~n-1，最后 [1] 结果+1 即为原问题的解

public class Yuesefu {

    /**
     * 构建循环链表
     * @param totalCol
     * @return
     */
    public node createNodes(int totalCol){
        node head = null; //定义一个头结点
        node[] nodes = new node[totalCol]; //数组结点存放 41 个人
        for(int i = 0; i < totalCol ; i++){
            nodes[i] = new node();
            nodes[i].node = i+1 ; //数据域赋值  不能让从 0 开始赋值 +1
            if(i==0){ //为 0 时就是是头结点
                // 初始化头结点
                head = nodes[i];
            }else{
                //当前下标结点的前一个节点对象的指针域指向当前 i 的结点
                nodes[i-1].next = nodes[i];
            }
        }
        nodes[totalCol-1].next = head ; //最后一个结点的指针域指向头结点
        return head ;
    }

public void begin(int total,int key){
        int sort = 0 ; //删除的序号
        int n = total ; //总人数
        node head = createNodes(total);
        //判断循环链表是不是只剩下一个节点
        while(head.next != head){
            for(int i = 1 ; i < key-1 ; i++){
                //1 ：每报数为 3 的人前一个节点 也就是 2 并替代当前头结点
                head = head.next;

            }
            //2：用一个临时节点代替为当前报数为 3 的结点
            node temp = head.next;
            System.out.println("第"+(++sort)+"个自杀的为："+temp.node);

            //3：使头结点的指针域指向报数为 3 的结点的 next 指向的结点
            head.next = temp.next;
            //替换头结点 等于当前报数为 3 的人结点  循环以上步骤直到最后一个结点自杀完毕
            head = head.next;

        }
        System.out.println("第"+(++sort)+"个自杀的为："+head.node);
    }

    public static void main(String[] args) {
        Yuesefu y = new Yuesefu();
        y.begin(41,3);
    }
}
class node {
    node next ; //指针域
    int node ; //数据域
    public node getNext() {
        return next;
    }
    public void setNext(node next) {
        this.next = next;
    }
    public int getNode() {
        return node;
    }
    public void setNode(int node) {
        this.node = node;
    }

}

算法流程如下：

• 1.初始化循环链表，从下标 1 开始自增赋值。头结点单数据域默认为空。单独处理不存放值
• 2.赋值到最后 totalCol-1 的结点 也就是尾部结点。它的指针域指向头结点形成单向循环链表。
• 3.循序开始判断链表是不是只剩下一个节点。也就是结点的指针域是否指向头结点。如果是就直接退出 while 并自杀此结点
• 4.当结点的指针域不是指向头结点时。循环操作 i<k-1 次循环找到当前报数为 3 的前一个节点。并使头结点替换
• 5 用一个临时节点代替为当前报数为 3 的结点（也就是步骤 4 找的结点的 next 指向）输出它已自杀
• 6.使头结点的指针域指向报数为 3 的结点的 next 指向的结点。最后替换头结点等于当前报数为 3 的人结点 循环以上步骤直到最后一个结点自杀完毕