小码农教环链 环链

发表于

「这是我参与11月更文挑战的第12天，活动详情查看：2021最后一次更文挑战」
[toc]

环链

环形链表

题目

image-20211025221103012

分析

image-20211025223634637

image-20211025225530551

我们剖析一下代码

image-20211025233902707 

1
2
3
4
5
6
7
8
9
10
11
c复制代码bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head,*slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            return true;
    }
    return false;
}

延伸问题：

1.为什么fast和slow会在环中相遇，会不会有这么一种情况呢。就是在环中一直交错永远遇不上？请证明一下。

结论：就上面fast和slow而言是一定相遇的

证明：

第一步：slow和fast，fast肯定是先进环，这时slow是fast入环前距离的一半。

第二步：随着slow进环，fast已经在环里走了一段了，走了 多少和环的大小有关系

第三步：我们这里假设slow进环的时候距离和fast是N

slow每次往前走1步，fast往前走两步，每追一次，判断一下相遇，结果为N-1，也就是说每追一次他们间的距离是一步一步的在减少，直到他们相遇

image-20211026071344761

这里就又衍生出了一个问题就是slow与fast只要是步差为一就可以相遇

2.为什么slow走一步，fast走两步呢？fast可不可以走大于两步呢？

结论：fast走n步，n>2,不一定会相遇

这里分析一个slow走一步，fast走三步的交错与不交错的情况

他们之间的距离变化是每次是两两的减少，这也就意味着可能会交错

image-20211026080439189

上面的奇偶问题也就又衍生出了N是他们的步差倍数就能相遇

环形链表 II

题目

image-20211026222807713

如何求环的入口点

分析

我们先直接放结论一个指针从相遇点开始走，一个指针从链表头开始走，他们会在环的入口点相遇

image-20211026233854511

image-20211026234236282 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c复制代码struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fast = head,* slow = head;
    while(fast && fast->next)
    {        
        fast = fast->next->next;
        slow = slow->next;      
        if(slow == fast)//相遇
        {
            //相遇节点
            struct ListNode * meetNode = fast;
            while(meetNode != head)
            {
                meetNode = meetNode->next;
                head = head->next;
            }
            return meetNode;
        }      
    }
    return NULL;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%