360网站建设服务器,做网站设计需要哪些软件,wordpress 即时通讯,网站不绑定域名解析环形链表必备的面试题和证明题#xff08;附图解#xff09; 文章目录环形链表必备的面试题和证明题#xff08;附图解#xff09;前言一、第一题1.题目2.思路3.代码4.延伸问题(1)证明题一#xff1a;(2)证明题二#xff1a;二、第二题1.题目2.思路延伸的证明题总结前言 …环形链表必备的面试题和证明题附图解 文章目录环形链表必备的面试题和证明题附图解前言一、第一题1.题目2.思路3.代码4.延伸问题(1)证明题一(2)证明题二二、第二题1.题目2.思路延伸的证明题总结前言
本文介绍环形链表相关的两道面试题以及延伸出来的证明题附源码图解 一、第一题
1.题目 141.环形链表 如下示例 给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。
为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始).
注意pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 否则返回 false 2.思路
slow和fast指向链表的开始slow一次走一步fast一次走两步不带环fast就会走到空带环fast会追上slow如下图 3.代码 代码如下示例 struct ListNode
{int val;struct ListNode *next;
};
bool hasCycle(struct ListNode *head)
{struct ListNode* slow head , *fast head;while(fast fast - next){slow slow - next;fast fast - next - next;if(slow fast){return true;}}return false;
}4.延伸问题
(1)证明题一 题目 如下示例 为什么slow和fast一定会在环中相遇会不会在环里面错过永远遇不上 结论 如下示例 他们一定会相遇但需要证明 分析证明 如下示例 (2)证明题二 题目 如下示例 为什么slow走一步fast要走两步能否fast一次走n步n2 结论 如下示例 当n2时不一定会相遇需要证明 分析证明 如下示例 二、第二题
1.题目 环形链表2 如下示例 给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。
为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从0开始。
如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。2.思路延伸的证明题 思路 / 结论 如下示例 一个指针从相遇点开始走一个指针从链表头部开始走他们会在环的入口点相遇 证明方法1如下图 证明方法2如下图 总结
以上就是今天要讲的内容本文介绍了环形链表必备的面试题和证明题附图解 如果我的博客对你有所帮助记得三连支持一下感谢大家的支持
