【LeetCode】环形链表+结论证明

简介: 【LeetCode】环形链表+结论证明

题目链接:环形链表


题目:给你一个链表的头节点 head ,判断链表中是否有环。


如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回 true 。 否则,返回 false 。


示例1:


ba5ec863ee484b4abed35cb3863da199.png


示例2:


7809da57033c4bfb97d66ac8462a33d5.png


  • 解体思路  快慢指针


分别定义 fast 和 slow 指针,两个指针同时从头节点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。fast或者fast->next走到空指针,则该链表无环.


bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* show = head;
    while(fast && fast->next)
    {
        fast = fast->next->next; //一次移动两步
        show = show->next;       //一次移动一步
       // 快慢指针相遇,说明有环
        if(fast == show)
            return true;
    }
    return false;
}


很多人会有疑问:

1、slow和fast一定会相遇吗?

2、slow走1步,fast走3步可以吗?


  • 问题一证明:


一定会,fast会先进环,slow会后进环,假设slow进环时,slow和fast之间的距离为N,slow进环以后,fast开始追击slow,slow每走1步,fast每走2步,他们之间距离缩小1,追击过程中,他们之间的距离变化:

N

N-1

N-2

......

2

1

0

到0时候fast就会追上了,所以fast指针每次移动两个节点,slow指针每次移动一个节点,只要有环是不会错过的,肯定是会相遇的。


  • 问题二证明:


不一定,fast会先进环,slow会后进环,假设slow进环时,slow和fast之间的距离为N,slow进环以后,fast开始追击slow,slow每走1步,fast每走3步,他们之间距离缩小2。他们之间的距离变化:(分奇偶数分析)

N -> 偶数  奇数

       N        N

       N-2     N-2

       N-4     N-4

       N-6     N-6

       ....       ....

       4         3

       2         1

       0        -1

   偶数:每次走fast每次走三步,slow每次走一步,要是有环也是会相遇的。

   奇数:会进入进入新一轮的追击,slow和fast的距离变成C-1 (假设C是环的长度),如果C-1是偶数那么下一轮可以追上,如果C-1是奇数那么永远追不上。


目录
相关文章
|
23天前
|
Java
环形数组链表(java)
环形数组链表(java)
11 0
|
18天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
18天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
18天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
19 2
|
1月前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
18天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
23天前
|
Java
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
8 0
|
23天前
|
存储 算法 C语言
【数据结构与算法 刷题系列】环形链表的约瑟夫问题
【数据结构与算法 刷题系列】环形链表的约瑟夫问题
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表