一:题目
二:思路
前提:该题已经声明了结构体,只是看不见,声明如下:
因为是从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;
}
标签:NULL,ListNode,cur,int,环形,next,链表,约瑟夫,struct From: https://blog.csdn.net/shylyly_/article/details/142597616