一,问题描述

图片.png

二,一般解法

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)
            {
                last.next=head.next;
                count=0;
            }else{
                last=last.next;
            }
            head=last.next;
        }
        return head;
    }

每一个结点,都要走m步,所有时间复杂度为O(m*n),进阶解法要求做到时间复杂度O(n)

三,进阶解法

3.1 分析

当给定结点的数量和报的数就可以确定最后幸存的结点
base case:当只有一个结点时,结点的编号为1,所以只要确定f(i)和f(i-1)的关系,就可以得出f(N)的结果(即在节点个数为n的情况下的幸存的结点的编号)

图片.png
图片.png
图片.png
设函数名为getLive(int i(元素的个数),int m(报数))
函数体
{

}