链表经典面试题--链表修至圆满

2024-06-20 12:36

本文主要是介绍链表经典面试题--链表修至圆满,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.环形链表

a.为什么一定会相遇,有没有可能会错过,永远追不上?请证明

 b.slow一次走1步,fast走3步  4步  5步  n步还一定追得上吗  请证明

2.环形链表2

3.随机链表的复制


1.环形链表

141. 环形链表 - 力扣(LeetCode)

 思路:

快慢指针,慢指针走一步,快指针走两步

进环以后快指针开始追击慢指针

当快指针能追上慢指针就证明链表带环

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

面试问题:

a.为什么一定会相遇,有没有可能会错过,永远追不上?请证明

 

 假设slow进环时,fast跟slow距离时N,fast追击slow的过程中距离变化如下:

N

N-1

N-2

...

2

1

0

 每追击一次,距离缩小1,距离为0就是追上了

 b.slow一次走1步,fast走3步  4步  5步  n步还一定追得上吗  请证明

假设slow进环时,fast跟slow距离时N,

fast追击slow得过程只距离变化如下:

偶数        奇数

N                N

N-2             N-2

N-4             N-4

...                ....

4                   3

2                   1

0                   -1

追上了          错过了---->进行新得一轮追击,距离变成C-1(假设C是环得长度)

                        两种情况:1.C-1是偶数  2.C-1是奇数

 总结:

1.N是偶数,第一轮就追上了

2.N是奇数,第一轮追击会错过,距离变成C-1

        a、如果C-1是偶数下一轮就追上了

        b、如果C-1是奇数,那么就永远追不上

结论:如果同时存在N是奇数且C是偶数,那么就永远追不上

 那么,N是奇数且C是偶数的情况是否一定存在呢?

 假设slow进环时,fast跟slow距离时N,

slow走的距离是:L

slow进环时,假设fast已经在环里面转了x圈

fast走的距离 : L + x * C + C - N

 假设fast走的距离是slow的3倍

3*L = L + x*C + C - N

||

2*L = (x+1)*C + C + N

||

偶数=(x+1)*偶数 - 奇数

 由此,N是1奇数时,C也是奇数;N是偶数是,C也是偶数

只有奇数-奇数才能等于偶数

(x+1)*偶数一定等于偶数

所以,N是奇数且C是偶数不能同时存在,永远追不上的条件不成立

结论:一定能追上

N是偶数第一轮就追上了

N是奇数第一轮追不上,C-1是偶数第二轮就追上了

2.环形链表2

142. 环形链表 II - 力扣(LeetCode)

 与上面一样

相遇时:slow走的路程:L+N; fast走的路程:L+x*C  + N

假设fast走的路程时slow2倍

2*(L+N) = L+x*C + N

||

L+N=x*C

||

L=x*C-N

||

L=(x-1)C + C - N

 

 由此,slow走到开始入环的第一个节点时恰好是head走到开始入环的第一个节点处

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

3.随机链表的复制

138. 随机链表的复制 - 力扣(LeetCode) 

 

 思路:

把每个拷贝节点连接到原节点的后面

控制random

把拷贝节点拿下来尾插成新链表,恢复原链表

struct Node* copyRandomList(struct Node* head) {//把每个拷贝节点连接到原节点的后面struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}//控制randomcur=head;while(cur){struct Node* copy = cur->next;//拷贝节点已经连接到原节点的后面if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;//复制链表random指向原链表random指向的节点的拷贝节点//copy->random=cur->random;//错误,不能指向原链表的节点}cur=copy->next;//继续往下遍历}//把拷贝节点拿下来尾插成新链表,恢复原链表struct Node* copyhead=NULL;//新链表头节点struct Node* copytail=NULL;//新链表尾节点cur=head;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(copytail==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}cur->next=next;//恢复原链表cur=next;}return copyhead;
}

感谢观看,再见

这篇关于链表经典面试题--链表修至圆满的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1078144

相关文章

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

荣耀嵌入式面试题及参考答案

在项目中是否有使用过实时操作系统? 在我参与的项目中,有使用过实时操作系统。实时操作系统(RTOS)在对时间要求严格的应用场景中具有重要作用。我曾参与的一个工业自动化控制项目就采用了实时操作系统。在这个项目中,需要对多个传感器的数据进行实时采集和处理,并根据采集到的数据及时控制执行机构的动作。实时操作系统能够提供确定性的响应时间,确保关键任务在规定的时间内完成。 使用实时操作系统的

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

一些其他面试题

阿里二面:那你来说说定时任务?单机、分布式、调度框架下的定时任务实现是怎么完成的?懵了。。_哔哩哔哩_bilibili 1.定时算法 累加,第二层每一个格子是第一层的总时间400 ms= 20 * 20ms 2.MQ消息丢失 阿里二面:高并发场景下引进消息队列有什么问题?如何保证消息只被消费一次?真是捏了一把汗。。_哔哩哔哩_bilibili 发送消息失败

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

zookeeper相关面试题

zk的数据同步原理?zk的集群会出现脑裂的问题吗?zk的watch机制实现原理?zk是如何保证一致性的?zk的快速选举leader原理?zk的典型应用场景zk中一个客户端修改了数据之后,其他客户端能够马上获取到最新的数据吗?zk对事物的支持? 1. zk的数据同步原理? zk的数据同步过程中,通过以下三个参数来选择对应的数据同步方式 peerLastZxid:Learner服务器(Follo

java常用面试题-基础知识分享

什么是Java? Java是一种高级编程语言,旨在提供跨平台的解决方案。它是一种面向对象的语言,具有简单、结构化、可移植、可靠、安全等特点。 Java的主要特点是什么? Java的主要特点包括: 简单性:Java的语法相对简单,易于学习和使用。面向对象:Java是一种完全面向对象的语言,支持封装、继承和多态。跨平台性:Java的程序可以在不同的操作系统上运行,称为"Write once,

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图: 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图