当前位置：首页 > news >正文

环形链表的约瑟夫问题

news 来源：原创 2024/9/28 14:42:29

一：题目

二：思路

前提：该题已经声明了结构体，只是看不见，声明如下:

因为是从0开始实现：

1：创建一个n个节点的循环链表，其值为1~n（假设n = 5）

如图：

代码如下：

struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));if (newnode == NULL){perror("malloc failed");return NULL;}newnode->val = i;newnode->next = NULL;return newnode;}
struct ListNode* CreatList(int n)
{int i = 1;struct ListNode* head = NULL;struct ListNode* tail = NULL;while (i <= n){struct ListNode* newnode = BuyNode(i++);if (tail == NULL){head = tail = newnode;}else{tail->next = newnode;tail = tail->next;}}tail->next = head;return head;
}

代码解释：

a：用了一个BuyNode函数，来创造节点

b：循环中BuyNode的参数是i++,得到的节点的值从1到n（因为i<=n）

第一次得到节点：

非第一次得到节点：tail进行移动就行。

c：最后得到的五个节点是一个单链表，需要tail的next指向head才能形成循环链表

2：约瑟夫函数的实现

假设m = 2 ，即报数到2的人离开

流程如下：

代码如下：

int ysf(int n, int m) {struct ListNode* head = CreatList(n);struct ListNode* cur = head;struct ListNode* prev = NULL;int i = 1;while (cur != cur->next){if (i == m){prev->next = cur->next;cur = prev->next;i = 1;}else{prev = cur;cur = cur->next;i++;}}return cur->val;}

代码解释：

1：cur的next是自己，就代表只有一个节点了，不再进入循环

2：i代表报数的数字，i没到2，则prev和cur双双向后移动

3：i到2，则进行cur节点的移除，然后根据题目要求，i=1，重新开始报数

4：最后只有一个节点，返回其值。

三：总代码

struct ListNode* BuyNode(int i)
{struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));if (newnode == NULL){perror("malloc failed");return NULL;}newnode->val = i;newnode->next = NULL;return newnode;}
struct ListNode* CreatList(int n)
{int i = 1;struct ListNode* head = NULL;struct ListNode* tail = NULL;while (i <= n){struct ListNode* newnode = BuyNode(i++);if (tail == NULL){head = tail = newnode;}else{tail->next = newnode;tail = tail->next;}}tail->next = head;return head;
}int ysf(int n, int m) {struct ListNode* head = CreatList(n);struct ListNode* cur = head;struct ListNode* prev = NULL;int i = 1;while (cur != cur->next){if (i == m){prev->next = cur->next;cur = prev->next;i = 1;}else{prev = cur;cur = cur->next;i++;}}return cur->val;}