约瑟夫环 OJ

大家好，又见面了，我是你们的朋友全栈君。

循环链表的应用，并且应为不带头节点的循环链表，首先创建一个循环链表，在函数JOHEPHUS中进行操作，主要就是用for找到要删除的元素（注意p==1单独考虑，for中p至少为2），删除元素并输出直至链表为空。

for(j=1;j<=p-1;j++)把寻找报数的位置和寻找要删除的节点的前驱结合在一个循环中，减少时间复杂度，因为第一次写我是在主函数中用r指向找到的要删除的节点，然后传入delete(&L,r)中删除，而在delete中，需要从头找r的前驱，再修改指针，会发现这其中两个寻找的过程是重复进行的，所以基于函数功能的思想将它结合在一起，放入JOHEPHUS中，

第一次写加入了initList，但由于没有头节点，只是将头指针赋为空指针，并没有意义，而调用函数会使时间增长，可以将这一步放入到creat函数中，判空函数也完全可以有while(cur.next!=cur)来表示，当然这个函数判断是否只剩一个元素了，也完全不用重新写delete，

#include<stdio.h>
#include<stdlib.h>
#define error -1
typedef struct LNode{

   int num;
   struct LNode *next;
}LNode,* Link;

void creat_list(Link *L,int n){

   *L=NULL;
   int i;
   LNode * s=(LNode * )malloc(sizeof(LNode));
   (*s).num=1;
   (*s).next=s;
   (*L)=s;   
  if(n>=2)
  {

   for(i=2;i<=n;i++)
    {

       LNode * w=(LNode * )malloc(sizeof(LNode));
       (*w).num=i;
       (*s).next=w;
       (*w).next=(*L);
       s=w;
    }
  }
}

void JOHEPHUS(Link *L,int n,int p){

    int j;
    LNode * cur=*L;
    LNode *r;
   if(p==1){

       while(n-1){

       printf(“%d “,(*cur).num);
       cur=(*cur).next;
       n–;
       }
     printf(“%d”,(*cur).num);
     }
  else//p>=2
{

  while((*cur).next!=cur)
  {

     for(j=1;j<=p-1;j++)
    {

      r=cur;
      cur=(*cur).next;
     }
     printf(“%d “,(*cur).num);
    (*r).next=(*cur).next;
    free(cur);
    cur=(*r).next;
  }//while
  printf(“%d”,(*cur).num);
}//else
}//JOHEPHUS

int main()
{

 int p,n;
 Link  L;
 LNode * cur;
if(scanf(“%d %d”,&n,&p)!=EOF)
{

   if(p>=1&&p<=5000 &&n>=1&&n<=3000)
    {

     creat_list(&L,n);
     JOHEPHUS(&L,n,p);
     }//if
}//if
return 0;
}