matlab 单例模式 less dynamic constructor cuda HammerJS alertifyjs 后台管理ui angularjs教程 ppt视频教程下载 jquery去掉空格 kafka默认端口 matlab停止运行命令 虚拟机重启命令 vm虚拟化引擎 oracle重命名表名 java使用redis ln函数图像 python面向对象 mysql 连接 python断言assert实例 python操作mysql python调用函数 python链接mysql数据库 python语言编程入门 python做界面 java基础 java数组输出 java的多线程 php网络编程 java项目下载 qq免安装版 小米手环充电多久 圆角矩形工具改变弧度 大数据之路 jsp源代码 autocad2004迷你版 unlocker下载 固态硬盘有什么用
当前位置: 首页 > 学习教程  > 编程语言

单链表判断环路——《力扣刷题之路》

2020/10/8 20:31:18 文章标签:

文章目录1. 题目要求2. 解决思路3. 实现代码1. 题目要求 给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 题目链接…

文章目录

  • 1. 题目要求
  • 2. 解决思路
  • 3. 实现代码

1. 题目要求

给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。
有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。

题目链接: https://leetcode-cn.com/problems/linked-list-cycle-lcci

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

2. 解决思路

试想,你偷了家里的零花钱,你爸发现了之后,准备追着你打。你和你爸只能沿着小区不停的跑,你的速度是你爸的2倍,但是在跑的过程中,两者是不能看到对方的,只有跑到一个地方相遇了之后,才能发现对方,然后你爸就逮住了你,后事自行想象…

我们假设你家周围的路有两种可能,一种是没有环路,一种是有环路。

  1. 如果没有环路,那你爸肯定逮不住你。
  2. 如果有环路,那你爸会不会逮住你呢?下面我们就来看看,如果存在一个环路,你到底能否逃脱你爸的手心。

答案是:你惨遭毒打。如果你俩都进入了环,你的速度又是你爸的2倍,所以你迟早会因为跑太快而追上你爸,所以你的毒打是自己二脚造成的。

下面具体分析一下整个过程吧:
在这里插入图片描述

也就是说,如果我们一开始用两个速度相差2倍的指针去遍历,如果有环的话,肯定会在C点相遇,就可以确定C点位置。

有了C点位置,结合最后一个式子可以知道,如果2人分别从A点和C点同时以相同速度出发,由于速度相同,所以相同时间内走过的距离肯定也是相同的,再加上最后一个等式,可以知道其中一个人到达B点的同时,另一个也刚好到B点,所以肯定也会在B点相遇。

3. 实现代码

因为是单链表,所以一个结点肯定不会有环,所以要先判断一下。具体C++代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next)
            return NULL;
        ListNode *fast,*low;
        fast = head;
        low = head;
        while(fast&&fast->next){
            fast = fast->next->next;
            low = low->next;
            if (fast==low)
                break;
        }
        if(fast!=low)
            return NULL;
        low = head;
        while(fast!=low){
            fast = fast->next;
            low = low->next;
        }
        return fast;
    }
};

本文链接: http://www.dtmao.cc/news_show_250321.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?