用环形链表实现约瑟夫环问题

1 typedef struct node 2 { 3     int data; 4     struct node * next; 5 }Node, *Link; 6  7 Link create(int n) //生成环形链表 8 { 9     Link head, rear ;10     Link p = new Node; //第n个节点11     p->data = n;12     head = rear = p;13     for( int i=n-1; i>0; i-- ) //从前面插入n-1个节点，注意，单项链表是便于逆向顺序构成的。 14     {15         p = new Node;16         p->data = i;17         p->next = head;18         head = p; //每插入一个节点，头指针前移一个19     }20     rear->next = head ; //n节点指向头节点，构成环形链表21     return h;22 }23 24 int joseph( int m, Link h ) //找出最后一个25 {26     Link p = h;27     int i=0;28     while( p->next != p ) //只有一个节点时结束循环29     {30         i++;31         if( i == m-1) //数了m-1个节点32         {33             Link q = p->next ; //删除下一个，即第m个34             p->next = q->next ;35             delete q;　　//因为结点都是new出来的内存堆区域里的空间，所以必须delete才能收回36             i = 0;  //删除一个节点，计数器置为037         }38         p =p->next ;39     }40     int last= p->data ;41     delete p;   //删除最后一个节点，避免内存泄露42     return last;43 }