<8> 单向循环链表在一些场景下的应用

我们经常会碰到类似“约瑟夫环”的问题，这类环类问题，一般可以使用单向循环链表来使用。

#include <iostream>
#include <malloc.h>


typedef struct Person
{
    int ID;
    Person *next;
}m_Person;


m_Person* CreateLinkedList(int number,int *array) {

    m_Person *head = NULL;
    m_Person *p1, *p2 = NULL;

    p2 = p1 = (m_Person*)malloc(sizeof(m_Person));
    p1->ID = array[0];
    
    for (size_t i = 0; i < number; i++){
        if (head == NULL) {
            head = p1;
            p2 = p1;
        }
        else{ 
            p1 = (m_Person*)malloc(sizeof(m_Person));
            p1->ID = array[i];
            p2->next = p1;
            p2 = p1;
        }
    }

    p2->next = head;
    p1 = NULL;
    free(p1);

    return head;
}

m_Person* isEnd(m_Person* L) {
    m_Person *Temp = L;
    while (Temp->next!=L) {
        Temp = Temp->next;
    }

    return Temp;
}

void Joseph(m_Person *L, int m) {
    
    m_Person *Current = L;
    
    m_Person *NewHead = L;
    
    if (NewHead != NULL) {

        while (NewHead->next != NewHead) {
            for (size_t i = 0; i < m - 1; i++) {
                Current = L;
                L = L->next;
            }

            if (NewHead == L) {
                m_Person* End = isEnd(L);
                std::cout << NewHead->ID << " ";
                End->next = NewHead->next;

                NewHead = NewHead->next;
                L = NewHead;
            }
            else {
                std::cout << L->ID << " ";
                Current->next = L->next;
                L = L->next;
            }
        }

        std::cout << NewHead->ID;
    }
}


int main() {
    
    int n,m;

    std::cin >> n >> m;
    int *p = new int[n];
    for (size_t i = 0; i < n; i++) {
        p[i] = i + 1;
    }

    m_Person *Head = CreateLinkedList(n, p);
    Joseph(Head, m);

    std::cin.get();
    std::cin.get();
}