题解 | #经典的约瑟夫环问题#

使用环形链表解决

#include <vector>
#include <algorithm>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x = 0) : val(x), next(nullptr) {}
};

ListNode* createNode(int value) {
    ListNode* newNode = new ListNode();
    newNode->val = value;
    newNode->next = nullptr; // 或者 newNode->next = NULL; 依编译器和标准库版本而定
    return newNode;
}

void createCircularLinkedList(ListNode*& head, int size) {
    if (size <= 0) return;

    head = new ListNode(0);
    ListNode* current = head;

    for (int i = 1; i < size; ++i) {
        ListNode* newNode = createNode(i);
        current->next = newNode;
        current = newNode;
    }

    // 将最后一个节点的 next 指针指向头节点，形成环形链表
    current->next = head;
}

void printCircularLinkedList(ListNode* head) {
    if (!head) return;

    ListNode* current = head;
    do {
        cout << current->val << " ";
        current = current->next;
    } while (current != head);
    cout << endl;
}

int findSurvivor(int n, int k, int m){
    ListNode* head = new ListNode(0);
    createCircularLinkedList(head, n);
    for (int i = 0; i < k; i++) {
        head = head -> next;
    }
    ListNode* current = head;
    ListNode* prev = nullptr;

    // 当只剩下一个节点时停止
    while (current->next != current) { // More than one node
        // Move m-1 times
        for (int count = 1; count < m; ++count) {
            prev = current;
            current = current->next;
        }
        // Remove current
        prev->next = current->next; // Skip the current node
        delete current; // Free memory
        current = prev->next; // Move to next
    }
    int result = current->val; // Last remaining node
    delete current; // Clean up
    return result;
}


int main() 
{
    int n, k, m;
    cin >> n >> k >> m;
    cout << findSurvivor(n, k, m) << endl;
    return 0;
}