力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题

这篇具有很好参考价值的文章主要介绍了力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法

为了加深对环形链表的理解和掌握,这两道题是很不错的选择。
这里所说环形链表不是一个圈圈的结构,而是带环链表。

链接:环形链表(1)

力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法
注意这里链表的长度
力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法
所以要注意链表是否为空
第一种方法,应该是比较容易想到的方法(偷鸡取脚)
 遍历链表,将每个节点的val更改为一个不容易想到的值,如666666,当遇到一个666666时就返回true,如果在遍历过程中一直走到空都再没有遇到一个666666,那就返回false。
代码如下

bool hasCycle(struct ListNode *head) {
    struct ListNode*p=head;
    while(p){
        if(p->val!=666666)
        {
            p->val=666666;
            p=p->next;
        }
        else 
        return true;
    }
    return false;
}

这种方法明显是投机取巧,所以还有可能被抓到。
运行后还是也可以通过
力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法
双指针法(正经方法)
 就想操场的跑道上,有跑的快的人和跑得慢的人,快的人会不断追上慢的人。
 设置双指针,从head开始走,快指针一次跑两步,慢指针一次跑一步,链表中是有环的,快指针一定会抓到慢指针。
 在慢指针进环时,快指针已经在环状里转圈圈了,慢指针一次走一步,快指针一次走两步,慢指针走半圈,快指针就走一圈。
力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法
代码如下

bool hasCycle(struct ListNode *head) {
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

一直找找找,如果有环一定会相遇。
思考:

如果快指针一次走3步,还可以保证能抓到慢指针吗?

 假使慢指针进环时,快慢指针差距m个位置,每次快指针与慢指针的距离差距减小为2,有两种情况。

  1. m为偶数

每次距离都减小2
m-2
m-4
m-6

4
2
0
最终快指针会遇到慢指针。
2. m为奇数
m-2
m-4

3
1
-1
当相差为-1时,快慢指针间的距离变为了m-1。
假设C是环的长度,这里的-1即为C-1;如果环的长度为偶数,那么快慢指针最近的距离为1,因为一次减小的距离为2,所以永远也追不上慢指针。


环形链表(2)
力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法
和第一道题不一样的是这道题如果有环,就返回入环的第一个节点,如果链表无环,就返回NULL。
接下来就要进行分析
 当快指针与慢指针相遇时,快指针所走的路程是慢指针的两倍。
 假设起点到入环口的距离是L,圆环的长度为C,入口点到相遇点的距离为x,这时通过分析就可以列出一个等式。
力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法
快指针的路程是慢指针的二倍

2(L+X)=L+n( C )+X
可得
L+X=n( C )
L=n( C )-X;

设置两个指针,第一个指针从起始位置出发,另一个指针从相遇点出发,他们就会在环的入口处相遇。
套用第一道题的思路,快慢指针相遇时找到相遇点,在设置两个指针分别出发,直到相遇,如果没有环的话就返回NULL;
代码如下

    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            struct ListNode*meet=slow;
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL; } 

提交后顺利通过。

环形链表的约瑟夫问题
链接:
环形链表的约瑟夫问题
力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题,leetcode,链表,算法
要使用单向链表实现。
 分析题目,构建一个链表,依次储存节点的位置,然后找到链表的尾,尾的next等于头节点,这样一个环形链表就构建成功了。
 从第一个节点开始往后走m-1步(数数时为m,因为第一个节点数1,所以往后走m-1到达目标节点),保存这个节点的next,将起始位置更改为该next,然后从新的起始位置继续往后边数,直到删除到只剩最后一个节点为止,假设这个节点为hei,那么循环结束的条件就是hei->next==hei,判断条件就是hei->next!-hei。

要注意
看代码,讲解很详细

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

typedef struct ListNode
{
	int val;
	struct ListNode* next;
}LN;

LN* Initnode()
{
	LN* head = (LN*)malloc(sizeof(LN));
	head->next = NULL;
	head->val = 0;
	return head;
}

LN* GetNewnode(int x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}
void Pushnode(LN* head, int x)
{
	assert(head);
	LN* pre = head;
	while (pre->next)
	{
		pre = pre->next;
	}
	pre->next = GetNewnode(x);
}

void Popnode(LN*head,LN* node)
{
	LN* cur = head;
	while (cur->next != node)
	{
		cur = cur->next;找到要删除的节点的前一个
	}
	LN* next = node->next;
	cur->next = next;
	free(node);
	node = NULL;
}


int main()
{
	int m, n;
	scanf("%d %d", &m, &n);
	//建立链表
	LN* head = GetNewnode(1);//第一个编号为1
	for (int i = 2; i <= m; i++)
	{
		Pushnode(head, i);//建立链表
	}
	//找尾
	LN* cur = head;
	while (cur->next != NULL)
	{
		cur = cur->next;
	}
	cur->next = head;
	//环形链表弄完
	//数数删位
	LN* hei = head;
	while (hei->next != hei)
	{
		for (int i = 1; i < n; i++)//因为移动三步,是移动量两次。
		{
			hei = hei->next;
		}
		LN* pop = hei;//找到要删除的节点pop
		hei = hei->next;//更换hei的位置
		Popnode(hei,pop);//删除pop。
	}
	printf("%d ", hei->val);//打印留下的节点的数值。
	return 0;
}

本文的讲解到这里就结束啦,鄙人才识短浅,如有错误还请多多指教。文章来源地址https://www.toymoban.com/news/detail-742113.html

到了这里,关于力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言数据结构-用链表解决约瑟夫环问题

    只是普通的大学生一枚,不会很牛的技巧和算法,只是在做数据结构作业中的一点感悟和思考。也不知道自己写得对不对,有什么意见和建议都可以直接指出来哦,我虚心接受(低头鞠躬.jpg)...... 试用线性表的链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下:设有

    2024年02月06日
    浏览(47)
  • 约瑟夫问题

    约瑟夫问题是一个经典的数学问题,也是计算机科学中常见的数据结构和算法题目之一。它的形式是:有n个人站成一排,从第一个人开始报数,每次报到m的人出列,直到所有人都出列为止。请问,最后留下的人原来在什么位置上? 这个问题可以用多种方法解决,其中包括使

    2023年04月09日
    浏览(33)
  • 约瑟夫环问题解决

    单链表 实现 错例 在使用malloc函数开辟的空间中,不要进行指针的移动, 因为一旦移动之后可能出现申请的空间和释放空间大小的不匹配 循环链表 单独创建 逐节点创建 约瑟夫环问题 实现方式一: 实现方式二: 删除节点并建立新链表 实现

    2024年02月02日
    浏览(46)
  • 约瑟夫环问题

    n n n 个人围成一圈,从第一个人开始报数,数到 m m m 的人出列,再由下一个人重新从 1 1 1 开始报数,数到 m m m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。 注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n − 1

    2024年02月02日
    浏览(36)
  • C语言:约瑟夫环问题详解

    前言 哈喽,宝子们!本期为大家带来一道C语言循环链表的经典算法题(约瑟夫环)。 据说著名历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人

    2024年04月13日
    浏览(33)
  • 循环链表解决约瑟夫环问题

    n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新从 1开始报数,数到 m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。 n个人围成一圈,很容易可以想到用循环链表解决问题,用结点代表每个人,节点的数据域存储人的编号

    2024年02月07日
    浏览(41)
  • 【算法】约瑟夫环问题解析与实现

    约瑟夫环(Josephus Problem)是一个经典的数学问题,涉及一个编号为 1 到 n 的人围成一圈,从第一个人开始报数,报到某个数字 m 的人出列,然后再从下一个人开始报数,如此循环,直到所有人都出列。本篇博客将详细解析约瑟夫环问题,并使用 Python 实现算法。 在约瑟夫环问

    2024年02月06日
    浏览(42)
  • 4种方法解决约瑟夫环问题

            约瑟夫环问题是大多数编程初学者必须要跨越的一道坎。在第一次见到它的时候,我还是个刚刚学会循环语句的小蒟蒻,而现在的我已经是深陷图论以及各种其他算法的大蒟蒻了(bushi)。可以说,约瑟夫环问题是我从编程基础向编程思维踏出的重要一步。        

    2024年02月12日
    浏览(32)
  • C语言 | 约瑟夫问题(猴王争夺战)

             约瑟夫问题有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。下面我们将用猴子争大王这一故事以及采用单向循环链表这一方法来进行讲解这一问题。         设编号为1,2,……n得n个猴子围

    2024年02月01日
    浏览(34)
  • 重温数据结构与算法之约瑟夫问题

    约瑟夫问题 ,是一个计算机科学和数学中的问题,在计算机编程的算法中,类似问题又称为 约瑟夫环 ,又称“丢手绢问题”。 据说著名犹太历史学家 Josephus 有过以下的故事: 在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也

    2024年02月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包