左神算法：环形单链表的约瑟夫问题（Java版）

本文主要是介绍左神算法：环形单链表的约瑟夫问题（Java版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题来自左神《程序员面试代码指南》“环形单链表的约瑟夫问题”题目。

题目

据说，著名犹太历史学家 Josephus 有过以下故事：

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

输入：一个环形单向链表的头节点 head 和报数的值 m。

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

进阶问题：如果链表节点数为 N，想在时间复杂度为 O(N)时完成原问题的要求，该怎么实现？

题解

普通解法

普通的解法就像题目描述的过程一样，具体实现请参看如下代码中的 josephusKill1 方法。

1．如果链表为空或者链表节点数为 1，或者 m 的值小于 1，则不用调整就直接返回。
2．在环形链表中遍历每个节点，不断转圈，不断让每个节点报数。
3．当报数到达 m 时，就删除当前报数的节点。
4．删除节点后，别忘了还要把剩下的节点继续连成环状，继续转圈报数，继续删除。
5．不停地删除，直到环形链表中只剩一个节点，过程结束。

/*** 循环报数，报到 m 的人自杀*/
public static Node josephusKill1(Node head, int m) {if (head == null || head.next == head || m < 1) {return head;}Node last = head;while (last.next != head) {last = last.next;}int count = 0;while (head != last) { // 直到仅剩一个为止if (++count == m) { // 正好数到 mlast.next = head.next; // 删除 head 所指向的节点count = 0; // 归零，下一个重新计数} else { // 继续往后数last = last.next;}head = last.next; // head 在前面走，last 在后面跟着}return head;
}

普通的解法在实现上不难，就是考查面试者基本的代码实现技巧，做到不出错即可。

很明显的是，每删除一个节点，都需要遍历 m 次，一共需要删除的节点数为 n-1，所以普通解法的时间复杂度为 O(n×m)，这明显是不符合进阶要求的。

下面介绍进阶的解法。

进阶解法

原问题之所以花费的时间多，是因为我们一开始不知道到底哪一个节点最后会活下来。所以依靠不断地删除来淘汰节点，当只剩下一个节点的时候，才知道是这个节点。如果不通过一直删除方式，有没有办法直接确定最后活下来的节点是哪一个呢？这就是进阶解法的实质。

举个例子，环形链表为：1->2->3->4->5->1，这个链表节点数为 n=5，m=3。通过不断删除的方式，最后节点 4 会活下来。但我们可以不用一直删除的方式，而是用进阶的方法，根据 n 与 m 的值，直接算出是第 4 个节点最终会活下来，接下来找到节点 4 即可。

到底怎么直接算出来呢？首先，如果环形链表节点数为 n，我们做如下定义：从这个环形链表的头节点开始编号，头节点编号为 1，头节点的下一个节点编号为 2，……，最后一个节点编号为 n。然后考虑如下问题：

最后只剩下一个节点，这个幸存节点在只由自己组成的环中编号为 1，记为 Num(1) = 1；
在由两个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是 Num(2)；
……
在由 i-1 个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是 Num(i-1)；
在由 i 个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是 Num(i)；
……

在由 n 个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是 Num(n)。
我们已经知道 Num(1) = 1，如果再确定 Num(i-1)和 Num(i)到底是什么关系，就可以逐渐求出 Num(n)了。下面是求解的过程。
首先来认识一个非常简单的函数 f(x)=x%i 的图像，如图 2-1 所示。

报数和编号之间的关系

假设现在圈中一共有 i 个节点，从头节点开始报数，报 1 的是编号 1 的节点，报 2 的是编号 2 的节点，那么报数和编号的关系如下。

举个例子，环形链表有 3 个节点，报 1 的是编号 1，报 2 的是编号 2，报 3 的是编号 3，报
4 的是编号 1，报 5 的是编号 2，报 6 的是编号 3，报 7 的是编号 1……
报数和编号的关系图如图 2-2 所示。




1．遍历链表，求链表的节点个数记为 n，时间复杂度为 O(N)。
2．根据 n 和 m 的值，还有上文分析的 Num(i-1)（新编号）和 Num(i)（老编号）的关系，依次求生存节点的编号。这一步的具体过程请参看如下代码中的 getLive 方法，getLive 方法为单决策的递归函数，且递归为 N 层，所以时间复杂度为 O(N)。
3．最后根据生存节点的编号，遍历链表找到该节点，时间复杂度为 O(N)。
4．整个过程结束，总的时间复杂度为 O(N)。

进阶解法的全部过程请参看如下代码中的 josephusKill2 方法。

代码

package chapter_2_listproblem;public class Problem_06_JosephusProblem {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}/*** 循环报数，报到 m 的人自杀*/public static Node josephusKill1(Node head, int m) {if (head == null || head.next == head || m < 1) {return head;}Node last = head;while (last.next != head) {last = last.next;}int count = 0;while (head != last) { // 直到仅剩一个为止if (++count == m) { // 正好数到 mlast.next = head.next; // 删除 head 所指向的节点count = 0; // 归零，下一个重新计数} else { // 继续往后数last = last.next;}head = last.next; // head 在前面走，last 在后面跟着}return head;}/*** 循环报数，报到 m 的人自杀*/public static Node josephusKill2(Node head, int m) {if (head == null || head.next == head || m < 1) {return head;}Node cur = head.next;int tmp = 1; // tmp -> list sizewhile (cur != head) {tmp++;cur = cur.next;}tmp = getLive(tmp, m); // tmp -> service node positionwhile (--tmp != 0) {head = head.next;}head.next = head;return head;}/*** 计算最终剩余的节点编号* 注：根据数学推理，杀死节点之前的老编号=（杀死节点之后的新编号+m-1）%i+1* @param i 圈中剩余节点数量* @param m 报数为 m 的自杀* @return 最终生存的节点*/public static int getLive(int i, int m) {if (i == 1) {return 1;}return (getLive(i - 1, m) + m - 1) % i + 1;}public static void printCircularList(Node head) {if (head == null) {return;}System.out.print("Circular List: " + head.value + " ");Node cur = head.next;while (cur != head) {System.out.print(cur.value + " ");cur = cur.next;}System.out.println("-> " + head.value);}public static void main(String[] args) {Node head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);head1.next.next.next = new Node(4);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = head1;printCircularList(head1);head1 = josephusKill1(head1, 3);printCircularList(head1);Node head2 = new Node(1);head2.next = new Node(2);head2.next.next = new Node(3);head2.next.next.next = new Node(4);head2.next.next.next.next = new Node(5);head2.next.next.next.next.next = head2;printCircularList(head2);head2 = josephusKill2(head2, 3);printCircularList(head2);}
}

这篇关于左神算法：环形单链表的约瑟夫问题（Java版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---