9度OJ 题目1189：还是约瑟夫环

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：341

解决：204

题目描述：

生成一个长度为21的数组，依次存入1到21；
建立一个长度为21的单向链表，将上述数组中的数字依次存入链表每个结点中；
将上述链表变为单向封闭(循环)链表；从头结点开始数，将第17个结点删除，将它的下一个结点作为新的头结点；
重复上述过程，直到该链表中只剩一个结点，显示该结点中存入的数字。

输入：

没有任何输入数据。

输出：

输出上面题目描述中最后剩下的节点中存入的数字。

样例输入：

样例输出：

提示：

请不要直接输出数据水过去，这样达不到提升自己的目的，
请按照题目要求来做题，这样到真正考试时才能应对自如。

来源：

2003-2005年华中科技大学计算机研究生机试真题

/**********************************   日期：2013-2-20*   作者：SJF0115*   题号: 九度OJ 题目1189：还是约瑟夫环*   来源：http://ac.jobdu.com/problem.php?pid=1189*   结果：AC*   来源：2003-2005年华中科技大学计算机研究生机试真题*   总结：**********************************/#include<stdio.h>#include<malloc.h>typedef struct Node{int data;struct Node *next;}LinkList;int main(){int i,count = 1;int n = 21;LinkList *head,*p,*newNode,*q;head = (LinkList*)malloc(sizeof(LinkList));head->data = 1;p = head;for(i = 2;i <= n;i++){//创建节点newNode = (LinkList*)malloc(sizeof(LinkList));newNode->data = i;//插入新节点newNode->next = p->next;p->next = newNode;p = newNode;}//使链表首尾相连，形成循环链表p->next = head;//从头结点开始数，将第17个结点删除，将它的下一个结点作为新的头结点；//重复上述过程，直到该链表中只剩一个结点，显示该结点中存入的数字。p = head;while(p->next != p){//找出第17个节点的前驱节点if(count == 16){count = 0;q = p->next;p->next = q->next;free(q);}p = p->next;count++;}printf("%d\n",p->data);return 0;}