c语言练习93：环形链表的约瑟夫问题

环形链表的约瑟夫问题

环形链表的约瑟夫问题_牛客题霸_牛客网

描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

示例1

输入：

5,2

返回值：

3

说明：

开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3      

示例2

输入：

1,1

返回值：

1

代码：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @param m int整型
 * @return int整型
 */
#include 
#include 
typedef struct ListNode ListNode ;
//创建结点
ListNode* ListBuyNode(int x) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    node->val = x;
    node->next = NULL;
    return node;
}
//创建带环链表
ListNode* CreatList(int n) {
//创建链表
    ListNode* phead = ListBuyNode(1);
    ListNode* ptail = phead;
    int i = 2;
    for (i = 2; i <= n; i++) {
        ListNode* node = ListBuyNode(i);
        ptail->next = node;
        ptail = ptail->next;
    }
    ptail->next = phead;
    return ptail;
}
int ysf(int n, int m ) {
    // write code here
    int count = 1;
    //刚开始的时候cur已经走到了套，头结点也会报数，所以count应该置为1
    //创建不带头的单向循环链表
    ListNode* prev = CreatList(n);
    //对链表进行约瑟夫游戏
    ListNode* cur = prev->next; //就是头结点
    while (cur->next != cur) {
        if (count == m) {
            prev->next = cur->next;
            free(cur);
            cur = NULL;
            cur = prev->next;
            count = 1;
        } else {
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
    return cur->val;
}

 野指针

野指针是指：没有指向有效内存位置的一个指针在作删除或释放对象的操作的时候，如果没有即时将指针的值置为NULL，或者有其他的有效内存地址的一个重新指向，那指针仍然指向之前释放后内存的存储位置，其就是野指针.