首页 > 其他分享 >142. 环形链表 II

142. 环形链表 II

时间:2023-04-06 23:57:53浏览次数:38  
标签:II head slow 142 nullptr fast next 链表 ListNode

 

解法一:①首先判断是否有环,若无环,则快指针或其下一指针指向空;若有环,则从快慢指针相遇的位置继续出发,直到再次相遇,遍历次数即为环长len。②两指针从头结点重新开始,让其中一指针先出发len步,而后另一指针再出发,相遇节点即为环起点。

/**
 * 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 == NULL || head->next == nullptr) return nullptr;
        ListNode* fast = head;
        ListNode*slow = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) break;
        }

        if(fast == nullptr || fast->next == nullptr) return nullptr;

        //快慢重新出发,再次相遇时slow所走步数为环长len
        fast = fast->next->next;
        slow = slow->next;
        int len = 1;
        while(fast != slow){
            fast = fast->next->next;
            slow = slow->next;
            ++ len;
        }
        //二指针回头节点,快指针先走环长len
        fast = head;
        slow = head;
        for(int i = 0; i < len; i ++ ){
            fast = fast->next;
        }
        while(fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

 解法二:优化的版本。x表示链表头到环起点距离,首次判环相遇点必然距环起点x。另其中一指针从头节点重开,同步同速启动直到相遇即可。

这里有点绕。

详细解释:假定链表起点到入环的第一个节点A的长度为a【未知】,到快慢指针相遇的节点B的长度为(a + b)【这个长度是已知的】。现在我们想知道a的值,注意到快指针p2始终是慢指针p走过长度的2倍,所以慢指针p从B继续走(a + b)又能回到B点,如果只走a个长度就能回到节点A。(假设环内剩余长度为c,则快指针走过的长度为: 2(a+b) = a + b + c + b 所以c=a)

注意一个容易忽略的点,当环非常小而链表非常长时存在快指针在环中遍历不止一次的情况,这样的话上面的a和b存在对环长取余的情况,不过不影响结果。

/**
 * 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==nullptr || head->next == nullptr) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) break;
        }
        if(fast == nullptr || fast->next == nullptr) return nullptr;

        fast = head;
        while(fast != slow){
            //slow在环内距起点x+cnt*环长,fast在链表头也距环起点x,同步,相遇。
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

 

标签:II,head,slow,142,nullptr,fast,next,链表,ListNode
From: https://www.cnblogs.com/luxiayuai/p/17294637.html

相关文章

  • 剑指 Offer 14- II. 剪绳子 II
    题目链接:剑指Offer14-II.剪绳子II方法:数论解题思路将\(n\)分为\(m\)个数的和,使得这\(m\)个数的乘积最大,那么应该将\(m\)个数分为\(2\)和\(3\)的组合,尽可能为\(3\)。注意大数越界问题。代码classSolution{public:intcuttingRope(intn){......
  • 链表练习4
    已知整型链表,设计算法,删除所有结点值为x的结点,删除的结点个数通过形参返回。#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;}Node,*LinkList;LinkListcreate(){LinkListh,r,s;h=(LinkList)malloc(sizeof(Node));r=h;inta;sc......
  • 树:剑指 Offer 68 - II. 二叉树的最近公共祖先
    题目描述:给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个结点p、q,最近公共祖先表示为一个结点x,满足x是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉树: root= ......
  • Rider-调试并配置本地IIS
    项目部署到IISIIS:新建Web站点,路径指向Web应用程序根目录,端口默认80端口;应用程序池:".NetCLR版本"选择.NetCLR版本v4.0.30319,托管管道模式选择"集成"。  Web项目配置在Rider中选中Web项目,输入F4,打开csproj文件,添加如下配置。1<WebProjectProperties>2<U......
  • 141. 环形链表
     141. 环形链表解法一:所到之处,寸草不生第一种解法自己写的,巧妙运用了链表的val,只要遍历过,就将节点的值设置为1e9,时间空间复杂度都达到了完美的统一(doge)/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*L......
  • 单向链表找到链表的中点
    偶数为n/2奇数为(n+1)/2点击查看代码ListNode*slow=head,*fast=head;while(fast->next!=nullptr&&fast->next->next!=nullptr){slow=slow->next;fast=fast->next->next;}注:需要判断头结点是否为空......
  • 修复typecho字体资源跨域加载报错(基于IIS)
    在前面的文章中介绍了如何在IIS中配置typecho站点。一切使用都比较顺利,最近发现如果我不是直接输入网址进入,而是通过其它方式进入时,字体资源就会找不到。 像下面这样  查了一下,反正是跨域相关的问题,在IIS中解决方法如下:         ......
  • 链表反转-JavaDG实现
    对于链表的反转,用常规的迭代法,是很简单的,使用两个指针;对于用递归法,则是很经典题了,我就觉得对于递归方法和常用的迭代法,大家最好都熟悉掌握,不要刻意的去避免哪一点;1•链表反转2○常规的迭代实现:3publicListNodereverseList(ListNodehea......
  • 单链表进阶OJ版--->随机指针问题
    朋友们,晚上好!!今天,推出一篇单链表的随机指针问题!!相较于之前的链表OJ题,本期的链表难度有所提升!!下面请看题:>有一个链表,链表每个结点额外增加一个随机指针random,并且随机指针可以指向链表的任何结点以及空结点至于本题的要求是:复制带随机指针的链表如下图所示:>本题的难度,大致......
  • 树:剑指 Offer 55 - II. 平衡二叉树
    题目描述:输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。示例1:  示例2:  限制:0<=树的结点个数<=10000 方法基于以下性质推出: 此树的深度 等于 左子树的深度 与 ......