约瑟夫问题

　　约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。最后只有1存活。

思路：用环链表实现，每计数到M，删除该处的节点，直到最后仅剩一个节点，输出节点的值，就是存活的人。

#include<iostream>
using namespace std;
typedef struct Node {
    int data;
    Node *next=NULL;

}Node;

 Node* creatLinkList(int n)
{
    
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = 1;
    Node *head = p;
    for (int i = 2; i <=n; i++)
    {
        Node *temp=(Node*)malloc(sizeof(Node));
        temp->data = i;
        p->next = temp;  
        p = p->next;   //每添加一个元素i，将p指向新增加的这个节点
    }
    p->next = head; //头尾相连，成环形链表
    return head;

}

 int solve(int n,int m)
 {
     if (m == 1 || n < 2)
         return n;
     Node *list_head = creatLinkList(n);
     //int i = 0;
     //while (list_head != NULL&&(i<n))
     //{
        // i++;
        // cout << list_head->data;
        // list_head = list_head->next;
     //}
     Node *cur=list_head;
     Node *temp = NULL;
     int count = 1;
     while (list_head->next!= list_head->next->next)   //判断头尾是否已经删到只剩一个节点了
     {
         if (count == m)
         {
             temp->next=cur->next;
             cur = temp->next;
             count = 1;
            
         
         }
         else
         {
             count++;
             temp = cur;   
             cur = cur->next;       //相当于temp存放的是cur的前一个节点

         }

     }
     return list_head->next->data;
 }

 int main()
 {
     int m;
     int n;
     cout << "input n and m:  " << "n代表环链表长度，m代表计数间隔" << endl;
     cin >> n >> m;
     int result = solve(n, m);
     cout << endl<< "result：" << result<<endl;


 }