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

struct soldier
{
    int num;
    struct soldier *next;
};
typedef struct soldier member;
typedef member* MEMBER;
MEMBER initial(int n);     //初始化链表，传入链表的结点个数，返回链表头结点
void Free(MEMBER headptr);   //删除释放链表

//current 当前结点  previous 前一结点  headptr 头结点
//total 结点个数 
int main()
{
    MEMBER current=NULL, previous=NULL, headptr=NULL;
    int i=0, j=0, m=0, total, a[10];

    printf("please input the number of soldiers:");
    scanf("%d", &total);
    headptr = initial(total);

    for(i=2; i<=total; i++)
    {
        current = headptr;
        while(current->num != i)   //将current指向到第i个结点
        {
            previous = current;
            current = current->next;
        }
        
        //若轮到删除第current个结点，且不是头结点（即加里森），则删除，并通过向后移5个结点，更新current的值找到下次需要删除的结点        
        while(current != headptr)  
        {
            current = current->next;
            previous->next = current;
            for(j=1; j<=4; j++)
            {
                previous = current;
                current = current->next;
            }
        }

        if(current->next == current)//若只剩下一个头结点，则i为所求值
            a[m++]=i;
        else  //否者此次尝试失败，重新进行下一次尝试，将链表恢复为初始状态
        {
            Free(headptr);
            headptr = initial(total);
        }
    }
    for(j=0; j<=m; j++)
        printf("the answer is %d",a[j]);
    return 0;
}

MEMBER initial(int n)
{
    int i;
    MEMBER headptr=NULL;
    MEMBER current=NULL, previous=NULL;
    headptr = (MEMBER) malloc (sizeof(MEMBER));
    if( headptr != NULL )  //创建头结点
    {
        headptr->num = 1;
        current = headptr;
        previous = current;
    }
    for(i=2; i<=n; i++)
    {
        current = (MEMBER) malloc (sizeof(MEMBER));
        if(current != NULL)   //内存分配成功后，将n个结点分别编号1~n
        {
            current->num = i;
            previous->next = current;
            previous = current;
        }
    }
    current->next = headptr;  //头结点与尾结点相连形成循环链表
    return headptr;
}

void Free(MEMBER headptr)
{
    MEMBER temp=NULL;
    temp = headptr;
    headptr = headptr->next;
    temp->next = NULL;
    while(headptr)  //若没有到最后一个结点，将各结点逐一释放
    {
        temp = headptr;
        headptr = headptr->next;
        if(temp != NULL)
            free(temp);
    }
}