使用链表解决约瑟夫环的问题

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

用在单链表中删除一个结点的思想来解决此题
设一个没有头结点指针的单链表。一个指针指向此单链表中间的一个结点（不是第一个，也不是最后一个结点），将该结点从单链表中删除，要求时间复杂度O（1）。
图示分析：

程序清单：

#include <iostream>
#include <malloc.h>
using namespace std;
typedef struct NODE
{
    int data;
    struct NODE *next;
}Node, *LinkList;
void CreatByTail(LinkList L)
{
    Node *p, *tail;
    tail = L;
    int i = 0;
while (i < 7)
    {
        p = (Node*)malloc(sizeof(Node));
        p->data = i + 1;
        tail->next = p;
        tail = tail->next;
        i++;
    }
    tail->next = NULL;
}
void OutPut(LinkList L)
{
    Node *p;
    p = L;
while (p != NULL)
    {
        cout << p->data << " -> ";
        p = p->next;
    }
    cout << "\b\b\b\b " << endl;
}
void Delete(LinkList L, Node *p)
{
    Node *late;
    late = p->next;
    p->data = late->data;
    p->next = late->next;
    free(late);
}
int main(void)
{
    LinkList L;
    L = (LinkList)malloc(sizeof(Node));
    L->data = 0;
    CreatByTail(L);
    OutPut(L);

    Node *p;
    p = L->next->next->next;
    Delete(L, p);
    OutPut(L);
return 0;
}

解决约瑟夫环的问题：
首先建立一个没有头指针的环形链表，并从1到length对其初始化，即为每个人的原始编号；
定义一个计数器count，若其指向待删除的前一个，则将它的下一个结点删除。
程序清单：

#include <iostream>
#include <malloc.h>
//链表解决约瑟夫环的问题
using namespace std;

typedef struct NODE
{
int data;
struct NODE *next;
}Node, *Linklist;

//尾插法建立一个环形链表
void CreatByTail(Linklist L, int length)
{
    Node *p, *tail;
    tail = L;
int i = 1;
while (i < length)
    {
        p = (Node*)malloc(sizeof(Node));
        p->data = i + 1;
        tail->next = p;
        tail = tail->next;
        i++;
    }
    tail->next = L;//使尾指针指向头结点，建立环形链表
}

void YueSeFu(Linklist L, int key)
{
    Node *cur;
    cur = L;
int count = 1;
while (cur->next != cur)//若相等，表明环中只剩最后一人，则循环结束
    {
//若计数到出局号码前一个的位置cur，则说明cur->next是需要被删除的结点
if (count == key - 1)
        {
//借助late记录cur->next的位置
            Node *late;
            late = cur->next;

//删除cur->next（即late）
            cur->next = late->next;
free(late);

//使count再从1开始计数，查找下一个出局号码
            count = 1;
            cur = cur->next;
        }
else
        {
            cur = cur->next;
            count++;
        }
    }
cout << "最后一个人原编号是： " <<cur->data << endl;
}
int main(void)
{
int length = 0;
int key = 0;
    Linklist L;
    L = (Linklist)malloc(sizeof(Node));
    L->data = 1;

printf("请输入人数： ");
scanf("%d", &length);
    CreatByTail(L, length);

printf("请输入出局编号： ");
scanf("%d", &key);
    YueSeFu(L, key);
return 0;
}

运行截图：