约瑟夫问题 利用循环链表进行解决 (JAVA)

首先要知道约瑟夫问题的来历

然后我们可以把这个问题转换一下

知道了具体思路以后，下面就可以进行代码的实现

//结点类
    private static class ListNode{
         ListNode next;
         T item;
        public  ListNode(T item,ListNode next){
            this.next=next;
            this.item=item;
        }

    }

首先呢，我们创建一个结点类

然后进行算法的实现

首先，我们可以创建两个结点，一个结点为另一个结点的上个结点

然后创建一个循环链表 

//创建第一给结点first
        ListNode first=null;
        //pre为first的上一个结点
        ListNode pre=null;
        //对链表进行遍历,使链表循环
        for (int i=1;i<=41;i++){
            if(i==1){
                first=new ListNode(i,null);
                pre=first;
                continue;
            }
            ListNode NewListNode = new ListNode(i,null);
            pre.next=NewListNode;
            pre=pre.next;
            if(i==41){
                pre.next=first;
            }

        }

有了循环链表，我们就可以对链表进行操作

 //设置一个计数常量
        int count=0;
        //进行问题解决
        //双指针方法
        //先创建两个虚拟指针
        ListNode n=first;
        ListNode before=null;
        //循环链表每隔三个结点删除一个结点，最后只剩下一个结点
        //当循环链表只剩下一个结点的时候，它本身的下一个结点的还是自己
        //n==n.next;
        while (n!=n.next){
            //用count进行报号
            count++;
            //当count等于3时，证明要删除这个结点
            //即让n的上一个结点指向n的下一个结点即可
            //同时count要重置为0
            //n要指向下一个结点
            //打印出要删除的结点
            if(count==3){
                before.next=n.next;
                System.out.print(n.item+",");
                n=n.next;
                count=0;
            }
            //当count不等于3时，n指向下一个结点，before指向n原来的结点
            else {
                before=n;
                n=n.next;

            }
        }
        //打印出最后剩余的那个结点
        System.out.println(n.item);

最后运算完成

看下结果

 可以看到

最后两个数字为16和31

分别是约瑟夫和他朋友所在的位置

证明我们的程序没有问题

下面给出源码

package linear;

import org.w3c.dom.Node;

import java.util.List;

public class JosephTest {
    public static void main(String[] args) {
        //创建第一给结点first
        ListNode first=null;
        //pre为first的上一个结点
        ListNode pre=null;
        //对链表进行遍历,使链表循环
        for (int i=1;i<=41;i++){
            if(i==1){
                first=new ListNode(i,null);
                pre=first;
                continue;
            }
            ListNode NewListNode = new ListNode(i,null);
            pre.next=NewListNode;
            pre=pre.next;
            if(i==41){
                pre.next=first;
            }

        }
        //设置一个计数常量
        int count=0;
        //进行问题解决
        //双指针方法
        //先创建两个虚拟指针
        ListNode n=first;
        ListNode before=null;
        //循环链表每隔三个结点删除一个结点，最后只剩下一个结点
        //当循环链表只剩下一个结点的时候，它本身的下一个结点的还是自己
        //n==n.next;
        while (n!=n.next){
            //用count进行报号
            count++;
            //当count等于3时，证明要删除这个结点
            //即让n的上一个结点指向n的下一个结点即可
            //同时count要重置为0
            //n要指向下一个结点
            //打印出要删除的结点
            if(count==3){
                before.next=n.next;
                System.out.print(n.item+",");
                n=n.next;
                count=0;
            }
            //当count不等于3时，n指向下一个结点，before指向n原来的结点
            else {
                before=n;
                n=n.next;

            }
        }
        //打印出最后剩余的那个结点
        System.out.println(n.item);

        }


//结点类
    private static class ListNode{
         ListNode next;
         T item;
        public  ListNode(T item,ListNode next){
            this.next=next;
            this.item=item;
        }

    }
}

约瑟夫算法有很多种实现方式

这里面只介绍了循环链表一种