外贸人常用网站,建设网站规模与类别,手机网站免费建设,无锡梅村网站建设环形链表的约瑟夫问题
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数#xff0c;报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后#xff0c;只剩下一个人#xff0c;问最后留下的这个人编号是多少#xff1f;
利用链表实现 思路#xff1…环形链表的约瑟夫问题
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后只剩下一个人问最后留下的这个人编号是多少
利用链表实现 思路1创建一个不带头单向循环链表需要注意的是链表创建后返回的结点是最后一个结点为的是链表可快速找到第一个结点和最后一个结点 2创建结构体指针prev和cur分别代表最后一个结点和第一个结点因为cur已经为第一个结点因此count1。遍历链表直到pcur的next还是pcur即链表中只含有一个结点时退出循环循环过程中当count为m时需要将当前位置的pcur置空count重置为1。不为count时只需将链表往后执行即可 3退出循环后返回cur-val即可 typedef struct ListNode ListNode;ListNode* ListBuyNode(int x){ListNode* node(ListNode*)malloc(sizeof(ListNode));if(node NULL){perror(malloc:);exit(1);}node-valx;node-nextNULL;return node; }ListNode* CreatList(int n)
{ListNode* headListBuyNode(1);ListNode* tailhead;for(int i2;in;i){ListNode* nodeListBuyNode(i);tail-nextnode;tailtail-next;}tail-nexthead;return tail;//
}int ysf(int n, int m )
{ListNode* prevCreatList(n);ListNode* curprev-next;int count1;while(cur-next ! cur){if(count m){prev-nextcur-next;free(cur);curprev-next;count1;}else {prevcur;curcur-next;count;}}return cur-val;
}利用循环语句实现 思路1利用i形成一个可循环遍历的类似圆形的数组 2利用j来判断报的数当报的数正好为m时将a[i]赋值为1并且不进行下面的循环直到数组中仅剩一个数组的值为0 3退出循环遍历数组输出值为0的数组的下标
#includestdio.hint main()
{int n 0;int m 0;scanf(%d %d,n,m);int a[30] { 0 };int count 0;int i 0;int j 0;while (count n - 1){i;if (in)i 1;if (a[i] 0){j;if (j % m 0){count;a[i] 1;j 0;}}}for (i 1; i n; i){if (a[i] ! 1){printf(%d\n, i);break;}}return 0;
}分割链表
给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有小于x的节点都出现在 大于或等于x的节点之前。 你不需要保留每个分区中各节点的初始相对位置。 思路1判断head是否为空空则直接返回head 2创建两个两个带头单向不循环链表一个存放小于x的值的结点一个存放大于等于x的值的结点。lesshead和greaterhead分别为两个链表的头结点lesstail和greatertail分别为两个链表的尾结点。 3创建一个pcur代替head进行链表遍历当pcur的val小于x时将pcur存入less链表大于等于x时将pcur存入greater链表 4遍历结束判断greatertail是否为空不为空则将greatertail的next赋值为空再将lesstail的next赋值为greatertail的next将大小链表连接在一起 5创建retail赋值为lesshead的next再将lesshead进行free置空最后返回retail即可
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{if(head NULL){return head;}ListNode* lesshead(ListNode*)malloc(sizeof(ListNode));ListNode* greaterhead(ListNode*)malloc(sizeof(ListNode));ListNode* lesstaillesshead;ListNode* greatertailgreaterhead;ListNode* pcurhead;while(pcur){if((pcur-val) x){lesstail-nextpcur;lesstaillesstail-next;pcurpcur-next;}else{greatertail-nextpcur;greatertailgreatertail-next;pcurpcur-next;}}if(greatertail)greatertail-nextNULL;lesstail-nextgreaterhead-next;ListNode* retaillesshead-next;free(lesshead);lessheadNULL;return retail;
}
