约瑟夫环详解

package newjosephu;

public class myfinaljosephu {
    //你可能会说crazy
    //我只想说ez！
    public static void main(String[] args)
    {
        circlelinkedlist list = new circlelinkedlist();
        list.add(100);
        //list.shownode();
        list.outnode(2,1);
    }

}
class circlelinkedlist
{
    node first  = null;
    public void add(int num)
    {
        node curnode = null;
        for(int i=1;i<=num;i++)
        {
            node s = new node(i);
            if(i==1)
            {
                first = s;
                first.next = first;
                curnode = first;
            }
            else
            {
                curnode.next = s;
                s.next = first;
                curnode = curnode.next;
            }
        }
    }
    public void shownode()
    {
        node s = first;
        while(true)
        {
            System.out.println(s.number);
            if(s.next==first)
            {
                break;
            }
            s = s.next;
        }
    }
    public void outnode(int count,int no)
    {
        //count 是数几次
        //sum 是有几个数，跟前面的比较
        //no 是从第几个开始数
        node helper = first;
        //helper是位于first之后的一个指针
        while(helper.next!=first)
        {
            helper = helper.next;
        }
        //从第几个人开始数
        for(int i=0;i<no-1;i++)
        {
            first = first.next;
            helper = helper.next;
        }
        //数几次--直到最后一个
        while(helper!=first)
        {
        for(int i=0;i<count-1;i++)
        {
            first = first.next;
            helper = helper.next;
        }
        System.out.println(first.number+"出圈了!");
        first = first.next;
        helper.next = first;
        }
        System.out.println("最后幸存的是"+first.number);
    }
}
class node
{
    int number;
    node next;
    public int getNumber() {
        return number;
    }
    public void setNumber(int number) {
        this.number = number;
    }
    public node(int number) {
        super();
        this.number = number;
    }
    public node getNext() {
        return next;
    }
    public void setNext(node next) {
        this.next = next;
    }

    public String toString() {
        return "node [number=" + number + "]";
    }
    
}

约瑟夫环问题

你可能会说crazy,但我只想说EZ。

• 具体问题 : 小朋友围成一圈,轮流报数，报到第n位的退出游戏，下一个小朋友继续从1开始报数，直到只剩下一个小朋友;

• 问题的本质是一个环形链表，我们不断遍历，直到这个环形链表只有一个元素

• 实现步骤

  1. 创建好一个环形链表

     • 构建一个表示链表头的first

     • 构建一个帮助我们的辅助节点cur

     • 最开始的时候，我们new一个节点，并把它给first和cur都附上值

     • cur现在代表我们正在构建的链表的第一个

     • 好的！，现在我们继续向里面增加节点

       1. 把节点连接到我们的环形链表上

       2. 让原来的老大让位，旧世界的余党该清除了!

       3. 这时候，我们的cur就派上用场了!

       4. cur.next = s

       5. S连接到头节点，形成闭环--s.next = first

       6. 现在s才是真正的第一，我cur要投奔你!

       7. cur = cur.next!

       8. 成功！恭喜我们！我们成功构建了一个环形链表

1. 好啦！我们拥有了一个环形链表，现在我们就可以进行之前的游戏了

   1. 首先我们先想想，因为我们要删除一个小朋友，就得让他之前的那个node的下一个不再指向它，这很容易理解，因为他已经退出游戏了，所以！我们需要两个指针--一个用来找到我们要退出游戏的小朋友，另一个就在前一个指针的后面，准备把这个小朋友之前的那个节点的指向从要退出游戏的小朋友的身上移开！

      所以--我们定义一个front，就是代表我们环形链表的开头，根据之前的分析，我们还需要ige指向front之后一位的节点

      所以我们定义一个helper来帮助我们，我们先让他加入我们的队伍--helper = front ，为了让他在front的背后，我们选择用while遍历，直到helper.next = front 说明helper已经来到了front的后一个，目的实现了!

1. 接着，准备工作完全完成，开始了游戏 。首先，我们要找到第一个开始的小朋友，因为不一定是从第一个小朋友开始的--这很ez

   我们只需用while循环，一个一个遍历即可

2. 接着选出人淘汰，由于第一个小朋友就会报1，如果我们逢2淘汰的话，那么我们的指针大队只用移动一位就可以了，所以

   i = 0;i<count-1;i++

   找到了要淘汰的就开始行动 头指针先离开

   head = head.next

   然后让后面的节点连接到头指针的新位置

   cur .next = head;

3. 如此重复，直到链表只剩下一个节点!;此时helper == first