草庐IT

【面试题】链表成环？求入环点？证明+代码？必须安排~

Weraphael 2023-12-21 原文

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：Leetcode + 面试/笔试
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨

标题

一、环形链表I

1.1 题目描述

LeetCode链接：环形链表I

1.2 思路 + 代码实现

【思路】
可以使用快慢指针，然后转化成追击问题。快指针一次走2步，慢指针一次走1步，如果链表成环，快指针就一定能追上慢指针。
此篇博客详细讲述了快慢指针 —> 点我跳转

【代码实现】

bool hasCycle(struct ListNode *head) 
{
    struct ListNode* fast = head,*slow = head;
    while (fast && fast->next)
    {
        //快指针一次走2步，慢指针一次走1步
        fast = fast->next->next;
        slow = slow->next;
        
        if (fast == slow)
            return true;
    }
    return false;
}

1.3 证明

写出以上代码并不难，关键在于证明。

  • 为什么慢指针slow走1步，快指针fast走2步，它们一定就能相遇？有没有可能会错过？请证明。

【证明】
假设慢指针slow进环时，设快指针fast和慢指针slow之间的距离是N，slow进环后，fast就开始追加slow，slow每走一步，fast就会走2步，它们之间的距离就会逐渐缩小1。
fast和slow之间的距离变化：
N — 起始距离
N-1
N-2
…
3
2
1
0 – 相遇
直到N的距离逐渐缩小到0，它们就一定能相遇。

  • 假设慢指针slow走1步，快指针fast走x步(x ≥ 3)，它们会相遇还是会错过？请证明。

【证明】
假设x = 3，与上面同样的道理，设slow进环时，fast和slow之间的距离为N。slow进环后，fast就开始追击slow，slow走1步，fast走3步，它们之间的距离就会逐渐缩小2。但这次的证明与上一个不同，因为上一个之间的距离逐渐缩小1，所以无论N的值是多少，N最后一定会被减到0。而这次证明需要对N进行分类讨论，N是偶数或奇数。
fast和slow之间的距离变化：
①当N是偶数时，再加上fast和slow的距离逐渐缩小2，最后的它们之间的距离一定为0
N — 起始距离
N - 2
N - 4
…
4
2
0 – 相遇
②当N是奇数时
N
N - 2
N - 4
…
3
1
-1
当走到最后，fast和slow之间的距离为-1，这说明fast在追加slow的时候超过slow了，此时fast和slow之间的距离就是周长 - 1(往后假设周长为C)，相当于进入新一轮追击。这里就要再判断C - 1是奇数还是偶数，如果C - 1是偶数代表一定能追的上，否则就追不上。

二、环形链表II

2.1 题目描述

LeetCode链接：环形链表II

2.2 思路 + 代码

【思路】
先给出结论：一个指针从相遇点开始走，另一个指针从起始点开始走。它们最终会在入环点相遇。 后面会给出i详细的证明过程

【代码实现】

struct ListNode *detectCycle(struct ListNode *head) 
{
    //快慢指针找相遇点
    struct ListNode* fast = head,*slow = head;
    while (fast && fast->next )
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            //相遇点（slow改成fast也行）
            struct ListNode* meet = slow;
            //记录起始点
            struct ListNode* start = head;
            while (start != meet)
            {
                meet = meet->next;
                start = start->next;
            }
            //最终他们会在入环点相遇
            return meet;
        }
    }    
    return NULL;
}

2.3 证明

面试官：你怎么知道一个指针从相遇点开始走，另一个指针从起始点开始走，它们最终会在入环点相遇。请证明


【证明过程】

  1. 设起始点->入环点的距离为L
    入环点->相遇点的距离为X
    环的长度为C
  2. 所以，慢指针移动的距离：L + X
    快指针移动的距离：L + nC + X

  • 为什么快慢指针相遇时，慢指针的移动距离小于环长，换句话说，为什么慢指针的移动距离不是L + X + n
    答：考虑最坏的情况下，当慢指针入环时，快指针敲好在慢指针前面，快指针则需要走C - 1步才能与慢指针相遇，所以无论对于任何情况，快指针到慢指针的距离都不会超过C - 1步，所以，慢指针的移动距离更不会大于环长

  • 快指针的移动距离不能写成L + C + X
    答：因为起始点到入环点和相遇点到入环点有可能不相等。

  1. 规定快指针走2步，慢指针走1步。所以，快指针的移动距离是慢指针的2倍。
    所以，不难可以列出等式：2(L + X) = L + nc + X
  2. 化简等式得：L = nC - X --> 意味着：一个指针从相遇点走，另一个指针从起始点走，它们最后会在入口点相遇。

5、总结

若证明过程有啥问题的，欢迎大佬指出，虚心接受orz

试题面spanclasstoken链表数据结构算法学习leetcode

有关【面试题】链表成环？求入环点？证明+代码？必须安排~的更多相关文章

  1. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  2. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  3. ruby-on-rails - 浏览 Ruby 源代码 - 2

    我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru

  4. ruby - 模块嵌套代码风格偏好 - 2

    我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的

  5. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  6. ruby - Net::HTTP 获取源代码和状态 - 2

    我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

  7. 程序员如何提高代码能力？ - 2

    前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源

  8. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  9. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

  10. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

随机推荐