成都创新互联网站制作重庆分公司

【链表问题】环形单链表约瑟夫问题

前言

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

站在用户的角度思考问题,与客户深入沟通,找到玉溪网站设计与玉溪网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站建设、网站制作、企业官网、英文网站、手机端网站、网站推广、域名申请网站空间、企业邮箱。业务覆盖玉溪地区。

【题目描述】

【链表问题】环形单链表约瑟夫问题

【要求】

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

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

【难度】

士:★☆☆☆

【解答】

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

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

代码如下

 1    //时间复杂度为O(n*m)的解决方法
2    public static Node josephusKill(Node head, int m) {
3        if(head == null || m < 1)
4            return head;
5        Node last = head;
6        //定位到最后一个节点
7        while (head.next != last) {
8            head = head.next;
9        }
10        int count = 0;
11        while (head.next != head) {
12            if (++count == m) {
13                head.next = head.next.next;
14                count = 0;
15            } else {
16                head = head.next;
17            }
18        }
19        return head;
20    }

由于有些手机可能会出现乱码问题,我这里再贴出图片:

【链表问题】环形单链表约瑟夫问题

这个方法的时间复杂度为 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.所以我们可以采用递归的方式来做。

代码如下:

 1   //时间复杂度为O(n)
2    public static Node josephusKill2(Node head, int m) {
3        if(head == null || m < 1)
4            return head;
5        int n = 1;//统计一共有多少个节点
6        Node last = head;
7        while (last.next != head) {
8            n++;
9            last = last.next;
10        }
11        //直接用递归算出目的编号
12        int des = f(n, m);
13        //把目的节点取出来
14        while (--des != 0) {
15            head = head.next;
16        }
17        head.next = head;
18        return head;
19    }
20
21    private static int f(int n, int m) {
22        if (n == 1) {
23            return 1;
24        }
25        return (f(n - 1, m) + m - 1) % n + 1;
26    }

图片代码:

【链表问题】环形单链表约瑟夫问题

问题拓展

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


本文标题:【链表问题】环形单链表约瑟夫问题
链接URL:http://cxhlcq.com/article/geohsg.html

其他资讯

在线咨询

微信咨询

电话咨询

028-86922220(工作日)

18980820575(7×24)

提交需求

返回顶部