约瑟夫环问题链表实现（Java）

墨蓝 2024-04-18 21:17 59阅读 0赞

面试中可能经常会遇到约瑟夫环问题，逻辑上很简单，就是看怎么实现了，一般而言，最简单最直观的就是利用链表，然后构建一个循环结构，正好是环，最后计算出结果。

遍历环形链表会是一个无限循环，如果链表中的数据逐渐减少，不控制终究会一个不剩，这又不满足我们问题的求解，因此我们需要定义出循环结束的条件，按照约瑟夫环的规则，只剩下一个的时候就结束，在环形链表结构中，那就是结点本身的下一个节点就是它自己。这样就可以结束遍历了。最后打印出剩下的结点，问题解决。

这里给出Java版本的实现：

package com.xxx.algorithm.wh;
    //约瑟夫环java实现
    //约瑟夫环问题的起源来自犹太历史学家约瑟夫和他的朋友以及39其余的犹太人，总共41人为了躲避敌人，藏在一个山洞中，
    //39个犹太人决定宁愿死也不被敌人抓到，于是决定自杀，所有人排成一个圈，由第一个人开始报数，每当数到3，就自杀。
    //这个游戏接着从自杀的位置开始，还是从1数到3。依次类推，约瑟夫将朋友和自己安排在了16和31的位置，最后顺利逃过了
    //自杀这一劫，因为最后就剩他一个人了。
    public class JosefCircleMain {
    	
    	public static void count(int n){
    		//数到3出局，中间间隔两个人
    		int k = 3;
    		//头结点不存储数据
    		Node head = new Node();
    		Node cur = head;
    		//循环构造这个链表
    		for(int i=1;i<=n;i++){
    			Node node = new Node(i);
    			cur.next = node;
    			cur = node;
    		}
    		//链表有数据的部分首尾相连形成一个环。
    		cur.next = head.next;
    		//统计开始的时候，刨去头结点，然后从第一个有数据的结点开始报数
    		Node p = head.next;
    		//循环退出的条件是最后只剩一个结点，也就是这个结点的下一个结点是它本身
    		while(p.next!=p){
    			//正常报数的遍历逻辑
    			for(int i=1;i<k-1;i++){
    				p = p.next;
    			}
    			//当数到3的时候，出局
    			System.out.print(p.next.data+"->");
    			p.next = p.next.next;
    			p = p.next;
    		}
    		//最后剩下的一个结点
    		System.out.println("(left:"+p.data+")");
    	}
    
    	public static void main(String[] args) {
    		//以4个人为例，1234 : 最先出局的是3，然后剩下412,接着2出局，剩下41，这时候就是4出局，最后剩下1.
    		count(4);
    		//41个人为例，就是约瑟夫环的本身了，最后剩下的是31
    		count(41);
    	}
    
    }
    
    class Node{
    	int data;
    	Node next;
    	public Node(){}
    	public Node(int data){this.data = data;}
    }

一般的链表，如果没有特别的说明，头结点是有数据的，但是这里情况比较特殊，我们构建了一个头结点没有数据的空节点，然后将链表的首尾相连，这个首其实也不是头结点，而是头结点的下一个结点，用图表示就是如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

首次遍历的时候，我们是从1开始的，所以代码中有这样的一句：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1][]

运行程序，打印结果：

3->2->4->(left:1)  
3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->35->16->(left:31)  
打印结果既验证了只有4个结点的情况，也验证了约瑟夫环的本身的结论。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c953ac4a14dd40f690a77bc8ebfec324.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5732aee025c24a978558c75d4f19b70c.png