约瑟夫环

#include<stdio.h>
typedef struct Node{
  int data;
  int id;
  struct Node *next;
}node;

#define SIZE sizeof(node)

node *initList();
void creatList(node *head, int n);
void printList(node *head);
node *jose(node *head,int password);
void printList_id(node *head);

int main(){
  int n,m;
  scanf("%d%d", &n, &m);
  node *head = initList();
  creatList(head,n);
  node *newhead = jose(head,m);
  printList_id(newhead);
}

//链表初始化
node *initList(){
  node *p;
  p = (node*)malloc(SIZE);
  p->next = p;
  return p;
}
//创建链表
void creatList(node *head, int n){
  node *new;
  node *pre;
  pre = head;
  int i = 1;
  while (n--) {
    new = (node*)malloc(SIZE);
    scanf("%d",&new->data);
    new->id = i;
    i++;
    pre->next = new;
    new->next = head;
    pre = new;
  }
}
//打印链表
void printList(node *head){
  node *cur = head->next;
  int i=0;
  while (cur != head) {
    i++;
    printf("i=%d,data=%d\n", i, cur->data);
    cur = cur->next;
  }
}

//打印链表id
void printList_id(node *head){
  node *cur = head->next;
  while (cur != head) {
    printf("%d ",cur->id);
    cur = cur->next;
  }
}
//判断空
int isEmptyList(node *head){
  if(head->next == head)
    return 1;
  return 0;
}
//约瑟夫环
node *jose(node *head,int password){
  node *newList = initList();
  node *pre = head;
  node *cur = head->next;
  node *Npre = newList;
  int count = 1;
  while (!isEmptyList(head)) {
    if(count == password){
      //重新计数
      password = cur->data;
      count = 0;
      //将cur从head链表中移除
      pre->next = cur->next;
      //将cur添加至newList
      Npre->next = cur;
      Npre = cur;
    }else{
      pre = cur;
    }
    cur = cur->next;
    //遍历至头节点
    if(cur == head){
      continue;
    }
    //head链表继续遍历
    count++;
  }
  Npre->next = head->next;
  head->next = head;
  Npre->next = newList;
  return newList;
}

#include<stdio.h>
typedef struct Node{
  int id;
  struct Node *next;
}node;

#define SIZE sizeof(node)

node *initList();
void creatList(node *head, int n);
node *jose(int n,int m);
void printList_id(node *head);

int main(){
  int n,m;
  scanf("%d%d", &n, &m);
  node *newhead = jose(n,m);
  printList_id(newhead);
}

//链表初始化
node *initList(){
  node *p;
  p = (node*)malloc(SIZE);
  p->next = p;
  return p;
}
//创建链表
void creatList(node *head, int n){
  node *new;
  node *pre;
  pre = head;
  int i = 1;
  while (n--) {
    new = (node*)malloc(SIZE);
    new->id = i;
    i++;
    pre->next = new;
    new->next = head;
    pre = new;
  }
}
//打印链表id
void printList_id(node *head){
  node *cur = head->next;
  while (cur != head) {
    printf("%d ",cur->id);
    cur = cur->next;
  }
}
//判断空
int isEmptyList(node *head){
  if(head->next == head)
    return 1;
  return 0;
}
//约瑟夫环
node *jose(int n,int m){
  node *newList = initList();
  node *head = initList();
  creatList(head,n);
  node *pre = head;
  node *cur = head->next;
  node *Npre = newList;
  int count = 1;
  while (!isEmptyList(head)) {
    if(count == m){
      //重新计数
      count = 0;
      //将cur从head链表中移除
      pre->next = cur->next;
      //将cur添加至newList
      Npre->next = cur;
      Npre = cur;
      //当cur指向head的下一个节点时
      if(cur == head->next)
        head->next = cur->next;
    }
    pre = cur;
    cur = cur->next;
    //遍历至头节点
    if(cur == head){
      continue;
    }
    //head链表继续遍历
    count++;
  }
  Npre->next = head->next;
  head->next = head;
  Npre->next = newList;
  return newList;
}