59 lines
1.7 KiB
C++
59 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
// https://blog.csdn.net/weixin_44412311/article/details/107432816
|
||
// https://blog.csdn.net/sdlwzzm19971226/article/details/79873900
|
||
/* 创建一个单链表 */
|
||
struct ListNode {
|
||
int num;
|
||
ListNode *next;
|
||
};
|
||
|
||
int main() {
|
||
int king, i;
|
||
//实例化头节点
|
||
ListNode *head = new ListNode; //完成了内存申请
|
||
//创建两个指针，指向头节点
|
||
ListNode *p, *q = head;
|
||
//第一个猴子的序号
|
||
head->num = 1;
|
||
//开始填充其它29只猴子
|
||
for (i = 1; i < 30; i++) {
|
||
p = new ListNode; //给新增加的节点分配空间
|
||
p->num = i + 1; //给结点数据域传值
|
||
//给新增加的节点加到链表的尾巴上
|
||
q->next = p;
|
||
//链表向后走一个，保持在最后一个节点上，方便下一次的增加
|
||
q = p;
|
||
}
|
||
//最后一个的尾巴接上head
|
||
q->next = head;
|
||
|
||
//开始进行淘汰
|
||
p = head;
|
||
for (i = 1; i < 30; i++) { //共淘汰29只
|
||
p = p->next; //p走1个
|
||
q = p->next; //q在p的基础上再走1个，这样就相当于到第3个猴子了，需要删除了。
|
||
printf("第%d轮淘汰第%d只猴子！\n", i, q->num);
|
||
p->next = q->next; //q->next:淘汰掉的猴子的下一只猴子, p->next = q->next 把淘汰掉的猴子的下一只猴子与淘汰掉猴子的前一只进行对接
|
||
p = q->next; //淘汰掉的猴子的下一只作为新的p
|
||
//销毁节点
|
||
delete q;
|
||
q = NULL;
|
||
}
|
||
//输出猴王
|
||
king = p->num;
|
||
//销毁节点
|
||
// 最好的方法避免野指针:标准姿势
|
||
// https://blog.csdn.net/u011301123/article/details/9293297
|
||
// https://blog.csdn.net/qwer1542112264/article/details/103524911
|
||
// https://www.cnblogs.com/uniqueliu/archive/2011/07/18/2109778.html
|
||
delete p;
|
||
p = NULL;
|
||
|
||
printf("猴王是第%d只！\n", king);
|
||
return 0;
|
||
}
|
||
|