【数据结构与算法】刷题篇——环形链表的约瑟夫问题

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构定义
typedef struct ListNode ListNode;
struct ListNode {
    int val;
    ListNode* next;
};

// 创建新节点
ListNode* buyNode(int i) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = i;
    newNode->next = NULL;
    return newNode;
}

// 创建环形链表
ListNode* createCircularLinkedList(int n) {
    if (n <= 0) return NULL;
    
    ListNode* newHead = buyNode(1);  // 创建头节点
    ListNode* newTail = newHead;     // 尾指针初始指向头节点
    
    // 依次添加节点并形成环形
    for (int i = 2; i <= n; i++) {
        newTail->next = buyNode(i);  // 创建新节点并链接
        newTail = newTail->next;     // 移动尾指针
    }
    newTail->next = newHead;         // 首尾相连形成环
    return newTail;                  // 返回尾节点（方便后续操作）
}

// 约瑟夫环求解函数
int ysf(int n, int m) {
    if (n <= 0 || m <= 0) return 0;  // 处理无效输入
    
    // 创建环形链表并初始化指针
    ListNode* prev = createCircularLinkedList(n);
    ListNode* pcur = prev->next;     // 当前指针指向第一个节点
    int count = 1;                   // 报数计数器
    
    // 循环直到只剩一个节点
    while (prev != pcur) {
        if (count == m) {
            // 移除当前节点
            ListNode* nextNode = pcur->next;  // 保存下一个节点
            prev->next = nextNode;            // 跳过当前节点
            free(pcur);                       // 释放当前节点
            pcur = nextNode;                  // 移动到下一个节点
            count = 1;                        // 重置计数器
        } else {
            // 继续报数
            count++;
            prev = pcur;                      // 前驱指针跟进
            pcur = pcur->next;                // 当前指针后移
        }
    }
    
    // 处理最后剩余节点
    int result = prev->val;   // 保存结果值
    free(prev);               // 释放最后一个节点
    return result;            // 返回幸存者编号
}

ListNode* createCircularLinkedList(int n) {
    // 创建节点1作为头节点
    ListNode* newHead = buyNode(1);
    ListNode* newTail = newHead;
    
    // 添加后续节点
    for (int i = 2; i <= n; i++) {
        newTail->next = buyNode(i);
        newTail = newTail->next;
    }
    
    // 形成环形结构
    newTail->next = newHead;
    return newTail;  // 返回尾节点
}

while (prev != pcur) {
    if (count == m) {
        // 移除当前节点
        ListNode* nextNode = pcur->next;
        prev->next = nextNode;
        free(pcur);
        pcur = nextNode;
        count = 1;
    } else {
        // 继续报数
        count++;
        prev = pcur;
        pcur = pcur->next;
    }
}

int result = prev->val;  // 保存结果值
free(prev);              // 释放最后一个节点
return result;

int josephus(int n, int m) {
    int result = 0;
    for (int i = 2; i <= n; i++) {
        result = (result + m) % i;
    }
    return result + 1;
}

printf("Josephus位置: %d\n", ysf(41, 3));  // 输出31