C语言练习（29）

13个人围成一圈，从第1个人开始顺序报号1、2、3。凡报到“3”者退出圈子，找出最后留在圈子中的人原来的序号。本题要求用链表实现。

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int num;
    struct Node* next;
} Node;

// 创建循环链表
Node* createList(int n) {
    Node* head, * p, * q;
    head = (Node*)malloc(sizeof(Node));
    head->num = 1;
    p = head;
    for (int i = 2; i <= n; i++) {
        q = (Node*)malloc(sizeof(Node));
        q->num = i;
        p->next = q;
        p = q;
    }
    p->next = head;
    return head;
}

// 执行报数并删除节点操作
Node* deleteNode(Node* head) {
    Node* p = head, * prev;
    while (p->next != p) {
        for (int i = 1; i < 3; i++) {
            prev = p;
            p = p->next;
        }
        prev->next = p->next;
        Node* temp = p;
        p = p->next;
        free(temp);
    }
    return p;
}

int main() {
    Node* head = createList(13);
    Node* last = deleteNode(head);
    printf("最后留在圈子中的人的原始序号是: %d\n", last->num);
    free(last);
    return 0;
}