数据结构——链表专题3

news/2024/9/23 9:35:02/

文章目录

  • 一、判断链表是否有环
  • 二、返回入环的第一个节点
  • 三、随机链表的复制

一、判断链表是否有环

原题链接:判断链表是否有环
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

这道题可以使用快慢指针,fast一次走两步,slow一次走一步,如果有环,它们在环里面必定会相遇

在这里插入图片描述

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

那么为什么一定会相遇呢?

对于快指针一次走两步来说,在slow进环后,假设slow与fast的距离为N

在这里插入图片描述

很明显,快指针走两步时,慢指针走一步,在进环后它们之间的差距为1,所以它们一定会相遇

那么快指针走三步?四步?五步呢?现在让我们证明一下:
现在我们规定快指针走三步,那么在进环后它们之间的差距为2

在这里插入图片描述
如果N是偶数那么在slow进环后一圈之内就能遇见fast
如果N是奇数那么在slow进环后一圈之内不能遇见fast,fast会超越slow一步,那么就不能相遇了吗?

在这里插入图片描述

假设在slow进环前,走过的距离是L,环的长度为C,fast在环内走过的距离为XC,slow进环时,slow与fast之间的距离为N

在这里插入图片描述
在这里插入图片描述

现在我们分析N是奇数的情况:
在这里插入图片描述

很好,现在我们只需要分析N为奇数时,C为偶数的情况是否存在?
在这里插入图片描述
结论:一定能追上
当N是偶数时,一轮就能追上
当N是奇数时,第一轮追不上,第二轮能追上

二、返回入环的第一个节点

原题链接:返回入环的第一个节点

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路:先使用快慢遍历链表,用meet指针指向它们相遇的结点,然后用pcur指针指向链表的头结点
最后让pcur和meet指针同时移动,每次移动一步,最终它们会在环的头结点相遇

在这里插入图片描述
在这里插入图片描述

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

证明:为什么meet指针一定与pcur指针在环头结点相遇?

假设在slow进环前,走过的距离是L,环的长度为C,fast在环内走过的距离为XC,
在slow位于链表的头结点时,fast与环的头结点之间的距离为N

在这里插入图片描述

三、随机链表的复制

原题链接:随机链表的复制

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路:
在原链表的基础上,在每个结点后面创建一个新结点,这个新结点保存着前面结点的数据
然后将新结点的random指针指向对应的位置
最后将新的结点从原链表上面脱离(此过程中可以选择恢复原链表),形成新的链表

在这里插入图片描述

struct Node* copyRandomList(struct Node* head)
{//拷贝原结点struct Node* pcur = head;while(pcur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));if(copy == NULL){exit(1);}copy->val = pcur->val;copy->next = pcur->next;pcur->next = copy;pcur = copy->next;}//拷贝random指针pcur = head;while(pcur){struct Node* copy = pcur->next;if(pcur->random == NULL){copy->random = NULL;}else{copy->random = pcur->random->next;}pcur = copy->next;}//脱离原链表pcur = head;struct Node* phead = NULL;struct Node* ptail = NULL;while(pcur){struct Node* copy = pcur->next;struct Node* next = copy->next;if(phead == NULL){phead = ptail = copy;}else{ptail->next = copy;ptail = ptail->next;}//恢复原链表pcur->next = next;pcur = next;}return phead;
}

http://www.ppmy.cn/news/1457407.html

相关文章

TCP经典异常问题探讨与解决

作者:kernelxing TCP的经典异常问题无非就是丢包和连接中断,在这里我打算与各位聊一聊TCP的RST到底是什么?现网中的RST问题有哪些模样?我们如何去应对、解决?本文将从RST原理、排查手段、现网痛难点案例三个板块自上而…

Python爬虫--Urllib基础

1. urlretrieve Urllib 库也是类似 request 库,用来解析html的 首先讲 urlretrieve 子模块 这个模块的作用是将网页下载到本地 语法: urlretrieve(网址,本地地址) 例如: 这样就可以了,他会将百度网页下载到本地D盘下&#x…

Spring AI

目录 一、Spring AI 1、Spring AI简介 1.1、四次工业革命发展和变革 1.2、什么是人工智能? 1.3、人工智能的发展历程 1.4、什么是大模型? 1.5、如何训练大模型? 一、Spring AI 1、Spring AI简介 Spring AI Java接入人工智能大模型 1.1、四次工业革命发展和变革 人类…

2024年4月17日华为春招实习试题【三题】-题目+题解+在线评测,2024.4.17,华为机试

2024年4月17日华为春招实习试题【三题】-题目题解在线评测 🔮题目一描述:扑克牌消消乐输入描述输出描述样例一样例二Limitation解题思路一:模拟,遇到连续3张相同牌号的卡牌,直接删除解题思路二:栈解题思路三…

pear + pecl 安装php扩展

pear https://pear.php.net/manual/en/installation.getting.php https://pear.php.net/go-pear.phar 让 CMD 支持 utf8 > chcp 65001 卸载 > php go-pear.phar uninstall 安装 > php go-pear.phar system 12 修改 12. Name of configuration file …

利用亚马逊云科技GenAI企业助手Amazon Q Business构建企业代码开发知识库

2024年五一节假日的前一天,亚马逊云科技正式重磅发布了云计算行业期待已久的服务——Amazon Q Business。Amazon Q Business是专为企业用户打造的一个开箱即用的完善而强大企业GenAI助手。企业用户只需要将Amazon Q Business连接到现有的企业内部数据源,…

NumPy及Matplotlib基本用法

NumPy及Matplotlib基本用法 导语NumPy导入与生成算术运算N维数组广播元素访问 Matplotlib简单图案绘制多函数绘制图像显示参考文献 导语 深度学习中经常需要对图像和矩阵进行操作,好在python提供了Numpy和Matplotlib库,前者类似一个已经定义的数组类&am…

RabbitMQ php amqp

Linux debian 安装 Windows php amqp 扩展 PECL :: Package :: amqp 将 php_amqp.dll 复制到 php 的 ext 目录下 将 rabbitmq.4.dll 复制到 c:\windows\system32 目录下 php.ini extensionamqp