单链表实现约瑟夫环问题

约瑟夫环

创新互联建站是网站建设专家,致力于互联网品牌建设与网络营销，专业领域包括网站制作、成都网站建设、电商网站制作开发、重庆小程序开发、微信营销、系统平台开发，与其他网站设计及系统开发公司不同，我们的整合解决方案结合了恒基网络品牌建设经验和互联网整合营销的理念，并将策略和执行紧密结合，且不断评估并优化我们的方案，为客户提供全方位的互联网品牌整合方案！

这里建议使用循环单链表

代码实现(c语言)

#include
#include

typedef struct node{  
	int data;      
	struct node *next;    
}Node;

void ysflb(int n,int k){//总共n,k出去
 //创建链表
  Node *head = NULL,*p = NULL,*r = NULL,*next = NULL;
  head = (Node *)malloc(sizeof(Node));  //开空间
  if(head == NULL){     //判断head是否创建成功，一般都成功
  	printf("Failed");
  	return;
  }
  
  head->data = 1;
  head->next = NULL; //这是第一个节点
  p = head;//p和head是同一个节点（指向）
 
  //循环，尾插
  for(int i = 2;i <= n; i++){
  	r = (Node *)malloc(sizeof(Node));
  	r->data = i;
  	r->next = NULL;
  	p->next = r;//p的next指向r，即将r连接再p的后面，一二节点连接完成。
	p = r;//将p向后移动一位，从第一个节点到了第二个节点   
  } 
    
   p->next = head; //让p的next指回去第一个节点
   p = head; //p再指向第一个节点

   //循环链表创建完成 
   
   while(p->next != p){//判断是否只剩一个元素
   	for(int i = 1;i < k;i++){
   		r = p; //r就是p的前一个节点，一会p会向后移动 
   		p = p->next;//p向后移动一位，p就是要出去的节点 
	   }
   	printf("%d\t",p->data); 
   	//删除p 
    //越过当前节点，将前一个节点于当前节点的后一个相连
    r->next = p->next;//前一个节点的next指向后一个节点的next
    p = p->next;//p向移一个节点（p成为当前节点的后一个节点）
    }
    printf("最后剩余："); 
    printf("%d",p->data); 
}


int main(){
	ysflb(10,3);
	return 0;
}