链表中环的入口结点

╰+哭是因爲堅強的太久メ 2023-02-20 12:17 31阅读 0赞

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

先找到环的节点数：一块一慢两个指针，快的追上慢的指针时，该指针指向的结点在环内，遍历一次环拿到节点数K，再用两个相距K的指针遍历一次链表，可找到入口结点。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
        
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        {
        
            if(pHead == NULL) return NULL;
            if(pHead->next == NULL) return NULL;
            ListNode *fast = pHead->next;
            ListNode *low = pHead;
            while(fast != low ) {
        
                if(fast->next == NULL || fast->next->next == NULL) return NULL;
                fast = fast->next->next;
                low = low->next;
            }
            fast = fast->next;
            int count = 1;
            while(fast != low){
        
                fast = fast->next;
                count++;
            }
            ListNode *res = pHead;
            while(count--){
        
                res = res->next;
            }
            while(pHead != res) {
        
                pHead = pHead->next;
                res = res->next;
            }
            return res;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 BM7 链表中环的入口结点

描述给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。数据范围： n\\le10000n≤10000，1<=结点值<=100001<

灰太狼/ 2023年10月04日 17:37/ 0 赞/ 57 阅读

相关链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。先找到环的节点数：一块一慢两个指针，快的追上慢的指针时，该指针指向的结点在环内，遍历一次环拿到节点

╰+哭是因爲堅強的太久メ/ 2023年02月20日 12:17/ 0 赞/ 32 阅读

相关链表中环的入口结点

![这里写图片描述][70] 一、分析判断链表有环的算法中出现过的策略，分别按1x和2x速度遍历，总会相遇。假设环长为n。容易知道，当1x的指针p1和2x的指针

今天药忘吃喽~/ 2022年05月24日 05:06/ 0 赞/ 197 阅读

相关编程题：链表中环的入口结点

题目描述一个链表中包含环，请找出该链表的环的入口结点。思路：假设x为环前面的路程，a为环入口到相遇点的路程， c为环的长度

╰+攻爆jí腚メ/ 2022年05月21日 09:45/ 0 赞/ 170 阅读

相关剑指offer:链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 AC C++ Solution: 解题思路：还是使用两个指针，一个fast，

小鱼儿/ 2022年04月10日 09:23/ 0 赞/ 218 阅读

相关【剑指Offer】（链表）链表中环的入口结点

题目链接：[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11

深藏阁楼爱情的钟/ 2022年03月17日 14:24/ 0 赞/ 246 阅读

相关剑指Offer-链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。解题思路—HashMap：使用HashMap存储链表结点，当链表结点重复时，即有环

曾经终败给现在/ 2022年02月14日 03:22/ 0 赞/ 229 阅读

相关链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 / @author gentleKay

た入场券/ 2021年11月09日 08:40/ 0 赞/ 298 阅读

相关剑指offer 链表中环的入口结点

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。链表结点定义

待我称王封你为后i/ 2021年11月05日 23:56/ 0 赞/ 303 阅读

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

试题：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。代码： / public class ListNode {

Myth丶恋晨/ 2021年06月24日 16:10/ 0 赞/ 412 阅读