公司做网站都需要什么流程,网站建设方案 预算,建网站公司要钱吗,肇庆建设工程备案的网站朋友们、伙计们#xff0c;我们又见面了#xff0c;本期来给大家解读一下LeetCode中的第141道单链表OJ题#xff0c;如果看完之后对你有一定的启发#xff0c;那么请留下你的三连#xff0c;祝大家心想事成#xff01; 数据结构与算法专栏#xff1a;数据结构与算法 个 … 朋友们、伙计们我们又见面了本期来给大家解读一下LeetCode中的第141道单链表OJ题如果看完之后对你有一定的启发那么请留下你的三连祝大家心想事成 数据结构与算法专栏数据结构与算法 个 人 主 页 stackY、 C 语 言 专 栏C语言从入门到精通 LeetCode--141.环形链表https://leetcode.cn/problems/linked-list-cycle/description/ 1.题目介绍 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 2.实例演示 3.题解思路 在这里如果使用最基础的方法来判断环形链表会比较麻烦而且办法也不是很多那么在这里小编给大家提供一种方法依旧是我们熟悉的快慢指针的方法 我们可以设置一个快指针和一个慢指针如果有环那么快指针和慢指针必定可以在环中相遇因为快指针的速度始终是慢指针的2倍所以快指针可以在环中追上慢指针我们先来使用这种比较简便的方法后面我们可以来验证一下 代码演示 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *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;
} 这种方法看似简单但是该如何证明呢我们接着往下看 4.拓展面试题 1. 假设有环快指针一次走一步慢指针一次走两步快指针一定会追上慢指针吗 快指针速度是慢指针的2倍所以快指针先进环慢指针后进环我们假设快指针和慢指针相距为N慢指针slow进环之后快指针fast开始追击慢指针slow快指针一次走两步慢指针一次走1步那么它们的距离随着它们走的步数会逐渐的缩小1就是一个公差为-1的等差数列那么只要走的步数够多快指针一定可以和慢指针相遇。 所以慢指针一次走一步快指针一次走两步一定会追上。 2. 假设有环如果快指针走任意步数慢指针走一步快指针能追上慢指针吗 在这里我们假设快指针一次走三步慢指针一次走1步。 快指针速度是慢指针的3倍所以快指针先进环慢指针后进环我们假设快指针和慢指针相距为N慢指针slow进环之后快指针fast开始追击慢指针slow快指针一次走3步慢指针一次走1步那么它们的距离随着它们走的步数会逐渐的缩小2就是一个公差为-2的等差数列这时我们需要计算一下它们之间的距离 快慢指针的距离会随着步数的增加最后变为-1这就表示会开始下一轮的追击那么下一轮的追击就可以分为两种情况 1. 假设环的周长为C那么快慢指针的距离就变为了C-1这时C-1如果为奇数那么永远追不上。 2. 假设环的周长为C那么快慢指针的距离就变为了C-1这时C-1如果为偶数那就就可以追上。 总结 1. 快指针一次走一步慢指针一次走两步快指针一定会追上慢指针。 2. 如果快指针走任意步数慢指针走一步快指针不一定能追上慢指针。 朋友们、伙计们美好的时光总是短暂的我们本期的的分享就到此结束最后看完别忘了留下你们弥足珍贵的三连喔感谢大家的支持
