单向链表解决约瑟夫问题

单向链表创建以及约瑟夫问题解决

package com.loopList;

public class LoopList {
    public static void main(String[] args) {
        Loop loop = new Loop();
        loop.AddNode(7);//创建num个单向环形链表
        loop.show_looplist();
        pop(loop.getFirst(),4,2);//拿到单向环形链表指向第一个结点的指针

    }

    /**
     *
     * @param first_nodes//创建链表，指向第一个结点的指针
     * @param start  //开始喊数字的位置
     * @param cur_num   //喊几个数
     */
    public static void pop(ListNode first_nodes,int start,int cur_num)//约瑟父问题
    {
        ListNode first_node=first_nodes;

        for (int i = 0; i <start-1 ; i++) {
            first_node=first_node.next;//将指针移动到要叫号的位置
        }

        ListNode assit_ptr=first_node;
            while (assit_ptr.next!=first_node)//为了将assit_ptr移动到环形最后一个结点上
            {
                assit_ptr=assit_ptr.next;
            }
            while (true)
            {
                if(first_node==assit_ptr)
                {
                    break;
                }
                for (int i = 0; i <cur_num-1 ; i++) {
                    first_node=first_node.next;
                    assit_ptr=assit_ptr.next;
                    System.out.println("孩子"+first_node.data+"出圈");
                }
                 first_node=first_node.next;
                assit_ptr.next=first_node;
            }
        System.out.println("孩子"+assit_ptr.data+"出圈");

    }
}
class ListNode//定义结点
{
    public int data;//结点中的值域
    public ListNode next;//结点中指向下一个节点的指针

    public ListNode(int data) {
        this.data = data;
    }
}

class Loop//定义一个环形单链表
{
    private ListNode first;

    public ListNode getFirst() {
        return first;
    }

    public void setFirst(ListNode first) {
        this.first = first;
    }

    public Loop()//单向环形链表的无参构造方法
    {
        first = null;//定义一个指向第一个结点的指针
    }

    public void AddNode(int num) {
        if (num < 1) {
            System.out.println("添加元素有误");
            return;
        }
        /**
         * 辅助指针
         */
        ListNode cur_boy = null;
        for (int i = 1; i <= num; i++) {
            ListNode boy = new ListNode(i);
            if (i == 1) {
                first = boy;
                first.next = first;
                cur_boy = first;
            } else {
                cur_boy.next = boy;
                boy.next = first;
                cur_boy = boy;

            }
        }


    }

    public void show_looplist()
    {
        if (this.first == null) {
            System.out.println("环形链表为空");
            return;
        }
        ListNode temp = first;
        while (temp.next != first) {

            System.out.println("结点的值=" + temp.data);
            temp = temp.next;
        }
        System.out.println("结点的值=" + temp.data);

    }

}
结果运行图：
结点的值=1
结点的值=2
结点的值=3
结点的值=4
结点的值=5
结点的值=6
结点的值=7
孩子5出圈
孩子7出圈
孩子2出圈
孩子4出圈
孩子1出圈
孩子6出圈
孩子3出圈