题解 | #环形链表的约瑟夫问题#

核心思想

• 成环， 返还tail结点
• 初始化前哨指针，和当前指针
• 遍历计数，当技术等于m了，则摘掉当前结点，从下个结点开始
• 返回最一个指针，即当前指针的val

/**
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
struct ListNode * createList(int n)
{
    int i = 1;
    struct ListNode * head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->val = i;
    head->next = NULL;
    struct ListNode * tail = head;

    i =2;
    while(i <= n)
    {
        struct ListNode * tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
        tmp->val = i;
        tmp->next = NULL;
        tail->next = tmp;
        tail = tmp;
        i++;
    }
    
    tail->next = head;
    
    return tail;
}

int ysf(int n, int m ) {
    // write code here
    // 成环
    if(n == 1)
    {
        return n;
    }
    
    
    struct ListNode * tail = createList(n);
    struct ListNode * move = tail->next;
    // 设置前哨结点，和当前的move结点
    
    int count = 1;
    while(move->next != move)
    {
        
        if(count == m)
        {
            tail->next = move->next;
            move = tail->next;
            count = 1;
        }
        count++;
        move = move->next;
        tail = tail->next;
        
    }
    
    return move->val;
}