有环链表

系统管理员 2022-05-15 21:49 154阅读 0赞

#### 写在前面 ####

> 剑指offer：链表中环的入口结点

#### 题目要求 ####

> 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

#### 解法 ####

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        {
            if(!pHead||pHead->next==nullptr) return nullptr;
            ListNode* fast = pHead, *slow = pHead;
            while(fast->next) {
                fast = fast->next->next;
                slow = slow->next;
                if(fast==slow) break;
            }
            if(!fast) return nullptr;
            fast = pHead;
            while(fast!=slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    };

> 分析：  
> 首先使用快慢指针，快指针一次走两步，慢指针一次走1步，当二者重合的时候说明有环。如果快指针已经到达nullptr说明无环。  
> 当第一次重合的时候该节点并不一定是环的入口节点。但是此时快指针走过的距离一定是慢指针走过的距离的两倍，稍微画图就可以看出，此时令其中一个指针返回起点，两个指针同时一步一步走当二者再次相遇的节点就是入口节点。

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关链表是否有环，以及环的位置

介绍两道算法题，与环形链表有关。 [LeetCode 141. Linked List Cycle（Easy）][LeetCode 141. Linked List C

水深无声/ 2023年02月08日 12:46/ 0 赞/ 14 阅读

相关链表是否有环

链表是否有环 1、参考资料 https://leetcode-cn.com/problems/linked-list-cycle/ 2、题目要求 > 题目描

墨蓝/ 2022年12月03日 15:46/ 0 赞/ 168 阅读

相关判断链表是否有环

/ 判断链表是否有环快慢指针 / public class Test2 { public static void main(S

Love The Way You Lie/ 2022年10月29日 07:45/ 0 赞/ 190 阅读

相关判断链表是否有环

//判断链表是否有环 public static boolean IsLoop(Node head){ Node fast =

深碍√TFBOYSˉ_/ 2022年10月01日 05:50/ 0 赞/ 99 阅读

相关判断链表是否有环

![这里写图片描述][70] //判断链表有环 public boolean hasCycle(ListNode head) {

忘是亡心i/ 2022年05月23日 04:42/ 0 赞/ 215 阅读

相关有环链表

写在前面 > 剑指offer：链表中环的入口结点题目要求 > 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。解法

系统管理员/ 2022年05月15日 21:49/ 0 赞/ 155 阅读

相关判断链表是否有环？

题目描述有一个单向链表，链表当中有可能出现“环”，就像下图这样。如何用程序判断出这个链表是有环链表？ ![70][] 方法一：首先从头节点开始，依次遍历单链表的每

你的名字/ 2022年05月14日 03:56/ 0 赞/ 235 阅读

相关判断链表是否有环

给定一个单链表，只给出头指针h： 1、如何判断是否存在环？ 2、如何知道环的长度？ 3、如何找出环的连接点在哪里？ 4、带环链表的长度是多少？解法

素颜马尾好姑娘i/ 2022年03月25日 14:42/ 0 赞/ 293 阅读

相关 leetcode 141. 环形链表（链表是否有环）

题目描述： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

缺乏、安全感/ 2022年02月26日 13:16/ 0 赞/ 297 阅读

相关判断链表是否有环，有环则找到入口

设置两个指针p1,p2，p1每次走1步，p2每次走2步。当p2能与p1相遇，表明存在环。设p1走了S步，则p2走了2S步，又因为p2比p1多走了环的长度，即环的长度

你的名字/ 2021年09月26日 15:16/ 0 赞/ 356 阅读