【链表】打卡5：环形单链表约瑟夫问题

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

【题目描述】

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报1，报数到3的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个自杀过程。

一般形式：

N个人围成一个圈，编号为1到N，从1号开始报数，报数为M的人出局；其他人继续围成圈，从出局人的下一个开始重新报数，报到M的人又出局。直到剩下最后一个人。

有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”。

【要求】

输入：一个环形单向链表的头结点 head 和报数 m.

返回：最后生存下来的结点，且这个结点自己组成环形单向链表，其他结点都删除掉。

【难度】

士：★☆☆☆

解答

方法1：时间复杂度为 O( n * m)

这道题如果不考虑时间复杂度的话还是挺简单的，就遍历环形链表，每遍历 m 个结点就删除一个结点，直到链表只剩下一个结点就可以了。

代码如下

//时间复杂度为O(n*m)的解决方法
public static Node josephusKill(Node head, int m) {
	if(head == null || m < 1)
		return head;
	Node last = head;
	//定位到最后一个结点
	while (head.next != last) {
		head = head.next;
	}
	int count = 0;
	while (head.next != head) {
		if (++count == m) {
			head.next = head.next.next;
			count = 0;
		} else {
			head = head.next;
		}
	}
	return head;
}

这个方法的时间复杂度为 O(n * m)。下面用时间复杂度为方法解决。

编号从0开始

通过数学方式可以提高算法的效率。可以将问题描述改为：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

注意这里的方法没有将每次报数人的编号计算出来，而是仅仅求出了胜利者的编号，下面算法的复杂度为O(n)。

当第一个人出列后（这个人的编号一定是（m - 1）% n，剩下的n - 1 个人重新构成了一个新的约瑟夫环（这个环以k = m % n开始报数）：

k，k+1，k+2，……，n-2，n-1，0，1，……，k-2。

将这n-1个人依次重新编号为0，1，2，……，n-1：

k —> 0，

k+1 —> 1，

k+2 —-> 2，

……

k-2 —> n - 2

即转换映射为 x —> (n + x - k - 1) % n == (x - k - 1) % n，反向的转换关系为： x <— (x + k + 1 - n) % n == (x + k + 1) % n

这些人继续从0号开始报数，那么，如果这n-1个人子问题的最后胜利者编号为f(n)。如果设n个人时胜利者编号为f(n - 1)的话，那么可以得到递推关系式：

f(n) = (f(n - 1) + k + 1) % n; 将 k = （m - 1）% n 代入， f(n) = ( f(n - 1) + (m - 1) % n + 1) % n = ( f(n - 1) + m) % n

也就是说，如果求得了n-1个人的胜利者根据递推关系式就可以求得n个人的胜利者，那么n-1个人的胜利者就通过求n-2个人的胜利者来求，因此这是递归过程。

解f(1) = 0; f(i) = (f(i - 1) + m) % i;(i > 1) 。这里的f(i)表示的是胜利者的编号。

推导：Josephus约瑟夫问题及其变种

注意这里的方法没有将每次报数人的编号计算出来，而是仅仅求出了胜利者的编号，下面算法的复杂度为O(n)。

方法二：时间复杂度为 O(n)

这个方法的难度为：

校：★★★☆

编号从1开始

我们可以给环形链表的结点编号，如果链表的结点数为 n, 则从头结点开始，依次给结点编号，即头结点为 1，下一个结点为2，最后一个结点为 n.

我们用 f(n) 表示当环形链表的长度为n时，生存下来的人的编号为 f(n)，显然当 n = 1 时，f(n) = 1。假如我们能够找出 f(n) 和 f(n-1) 之间的关系的话，我们我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为

…

m - 2

m - 1

m + 1

m + 2

…

进行了一次删除之后，删除了编号为m的结点。删除之后，就只剩下 n - 1 个结点了，删除前和删除之后的编号转换关系为：

删除前 — 删除后

… — …

m - 2 — n - 2

m - 1 — n - 1

m — 无(因为编号被删除了)

m + 1 — 1(因为下次就从这里报数了)

m + 2 — 2

… — …

新的环中只有 n - 1 个结点。且编号为 m + 1, m + 2, m + 3 的结点成了新环中编号为 1， 2， 3 的结点。

假设 old 为删除之前的结点编号， new 为删除了一个结点之后的编号，则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.

这样，我们就得出 f(n) (old)与 f(n - 1)(new)之间的关系了，而 f(1) = 1。所以我们可以采用递归的方式来做。

编号从0开始：f(n) = [f(n-1) + m] % n

编号从1开始：f(n) = [f(n-1) + m-1] % n + 1

代码如下：

//时间复杂度为O(n)
public static Node josephusKill2(Node head, int m) {
    if(head == null || m<1){
        return head;
    }
    int len = 1;//计算链表的长度
    Node last = head;
    while(last.next != head){
        len++;
        last = last.next;
    }
    //直接计算出目的结点的编号
    int des = f(len,m);
    //把目的结点取出来
    while(--des != 0){//循环des-1次
        head = head.next;
    }
    head.next = head;
    return head;
}

private static int f(int n,int m){
    if(n == 1){
        return 1;
    }
    //old:f(n)和new:f(n-1)的关系：f(n)=[f(n-1)+m-1]%n+1
    return (f(n-1,m)+m-1)%n+1;
}

测试代码

public static void main(String[] args) {
    int i = 1;
    Node head = new Node(i);
    Node node = head;
    while(++i<6){
        node.next = new Node(i);
        node = node.next;
    }
    node.next = head;
    node = josephusKill2(head, 3);
    System.out.println(node.value);
}

问题拓展

对于上道题，假设是从第 K 个结点开始报数删除呢？又该如何解决呢？

f(n) f(n-1)

… …

k+m-2 n-1

k+m-1 删除

k+m 1

k+m+1 2

… …

推导过程：关于递推算法求解约瑟夫环问题P(n,m,k,s)

两种递归方式：

/**
  * Josephus 环的一个O(N)算法
  * https://blog.csdn.net/sun_star1chen/article/details/17567451
  * https://www.kancloud.cn/digest/pieces-algorithm/163605
  * @param n 总人数
  * @param m 数到m的人出列
  * @param k 开始报数人的编号
  * @return 最后一个出列的编号
  */
public static int josephusON(int n, int m, int k) {
    int p = 0;
    for (int i = 2; i <= n; i++) {
        //出列的序列
        //System.out.print((p + k == n ? n : (p + k) % n)+"  ");
        p = (p + m) % i;
    }
    return p + k == n ? n : (p + k) % n; // 返回最后一人的位置
}

/**
  * https://blog.csdn.net/gesanghuazgy/article/details/49688433 
  */
public static int josephusON2(int n, int m,int k) {
    if(k==1)
        return (n+m-1)%n;
    else
        return (josephusON2(n-1,m,k-1)+m)%n;
}