首页 > 其他分享 >环形链表的约瑟夫问题

环形链表的约瑟夫问题

时间:2024-09-27 17:21:41浏览次数:9  
标签:NULL ListNode cur int 环形 next 链表 约瑟夫 struct

一:题目

二:思路

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

因为是从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

相关文章

  • 数据结构编程实践20讲(Python版)—02链表
    本文目录02链表linked-listS1说明S2示例单向链表双向链表循环链表S3问题:反转单向链表求解思路Python3程序S4问题:双向链表实现历史浏览网页求解思路Python3程序S5问题:基于循环链表的玩家出牌顺序求解思路Python3程序往期链接01数组02链表linked-lis......
  • 数据结构——链表
    c++数据结构p3链表链表的每一个节点都是独立分配出来的从当前节点能够找到下一个节点Node(链表)=date(数据域)+next(地址域)地址域:存储的是下一个节点的地址最后一个地址域是nullptrstructNode{intdata;Node*next;}特点:每一个节点都是在堆内存上独立new出来......
  • 【LeetCode Hot 100】21. 合并两个有序链表
    题目描述最简单粗暴的想法是将两个链表的所有元素拿出来放在一个数组中,再将此数组排序,最后生成一个新链表并返回。由于给出的参数本身就是两个排好序的链表,可以进行一次遍历,就能保证元素仍然是有序的:每次比较当前指针指向的两个元素的大小,较小的拿出来作为当前元素并将指针向前移......
  • [Python手撕]重排链表
    #Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defreorderList(self,head:Optional[ListNode])->None:""&quo......
  • 链表
    链表SingleListArrayList的缺陷在熟悉并且自己写了一个ArrayList顺序表的底层架构的时候发现ArrayList是利用数组来存储数据的效率比较低:这里说两个例子在插入以及删除的时候ArrayList都需要移动剩余的元素在开始的时候设置了初始的内存后续需要扩容这里也是效率低......
  • 算法记录——链表
    2.链表2.1判断是否是回文链表1.方法一:利用栈反转链表/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode(intval,Lis......
  • 【数据结构.总集篇】第一章 链表
    文章目录1.链表1.1线性表1.2顺序表1.3单链表链表简介单链表的介绍线性表的链式存储头节点概念为何引入头结点单链表的基本操作创建一个单链表初始化头插法尾插法删除操作打印总代码1.4单链表循环1.5双链表双链表的定义双链表上的操作初始化插入操作头插法尾插法......
  • 925 jdbc js 链表(2)
    jdbc基础复习一遍js声明函数行为绑定onclick单击ondbclick双击script标签放head以外也可以script必须写双标签变量声明都用var弱类型console。log1==1true1==‘1’trueprompt弹窗输入for循环js创建对象......
  • 【LeetCode Hot 100】19. 删除链表的倒数第N个结点
    题目描述由于单向链表只能从头往后遍历,所以无法向数组那样的随机存取结构一样进行下标运算,也无法从链表尾向前数n个结点。本题有两个思路,个人觉得都比较简单。可以先遍历一遍链表得到链表的长度len,然后再从头往后数len-n个结点就是所求结点。可以使用快慢指针,快指针先移动n......
  • 只用单链表的方式判断一个链表是否为回文链表
    思路寻找链表的中点:使用快慢指针的方法,快指针每次移动两步,慢指针每次移动一步。当快指针到达链表末尾时,慢指针正好位于链表的中间。反转后半部分链表:从中点开始反转链表的后半部分。比较前半部分和反转后的后半部分:逐一比较两个部分的节点值,如果所有对应的节点值都相同,则......