#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;
}