链表训练4：环形单链表约瑟夫问题
【题目描述】
【要求】
输入：一个环形单向链表的头节点 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;
}
System.out.println(head.value);
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)。下面用时间复杂度为方法解决。
方法二：时间复杂度为 O(n)
我们可以给环形链表的节点编号，如果链表的节点数为 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
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) 与 f(n – 1)之间的关系了，而 f(1) = 1.所以我们可以采用递归的方式来做。
代码如下：
//时间复杂度为O(n)
public static Node josephusKill2(Node head, int m) {
if(head == null || m < 1)
return head;
int n = 1;//统计一共有多少个节点
Node last = head;
while (last.next != head) {
n++;
last = last.next;
}
//直接用递归算出目的编号
int des = f(n, m);
//把目的节点取出来
while (--des != 0) {
head = head.next;
}
head.next = head;
return head;
}
private static int f(int n, int m) {
if (n == 1) {
return 1;
}
return (getDes(n - 1, m) + m - 1) % n + 1;
}另外，约瑟夫这道题一定要掌握递归版本的，因为递归版本是最不容易出错的，这道题的考察频率也是挺高的
关于约瑟夫问题，我还写过用一行代码直接搞定约瑟夫问题的，可以用来装逼：记一次阿里笔试：一行代码解决约瑟夫环问题的
问题拓展
对于上道题，假设是从第 K 个节点开始报数删除呢？ 又该如何解决呢？
如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….