循环链表应用——约瑟夫环问题

问题：已知n个人（以编号1，2，3，…，n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从K开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列

#include <iostream>

using namespace std;

struct node
{
    int data;
    struct node *next;
};

//约瑟夫环问题，n为总人数，k为第一个报数的人，m为出列者喊到的数
void josephus(int n, int k, int m)
{
    struct node *head=NULL, *p, *r;  //head为头节点，p指向当前节点，r指向p的前一个节点
    int i=1;

    //建立循环单链表，值分别为（1，2，3，4........n）
    p = r = new node;
    while(i <= n)
    {
        p->data = i;
        p->next = NULL;
        if(head==NULL)    //当前链表为空
            head = p;
        else
            r->next = p;
        r = p;
        i++;
        p = new node;
    }
    r->next = head;     //r为链表最后一个节点
    p = head;

    //寻找到第k个位置，p为寻找到的报数初始位置，r为p的前一个节点
    i = 1;
    while(i != k)
    {
        r = r->next;
        p = p->next;
        i++;
    }

    //逐一输出并删除节点，直到链表为空
    i = 1;
    while(r->next != r)
    {
        if(i == m)
        {
            cout<<p->data<<endl;        //输出节点值
            r->next = p->next;
            delete(p);
            p = r->next;
            i = 1;
        }
        else
        {
            i++;
            p = p->next;
            r = r->next;
        }
    }
    cout<<r->data<<endl;
}

int main()
{
    josephus(13,4,2);
    return 0;
}