当前位置：首页 > article >正文

ListOJ13：环形链表(判断是否为环形链表)

article 2025/1/27 17:06:18

题目描述

原题链接：141. 环形链表
在这里插入图片描述

思路分析

这题代码十分简单，重要的是这题中的思想，所以我们先看代码,再理解问题：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
    ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast -> next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}

这题的代码十分好理解，也就是：

1、首先，让快慢指针fast、slow指向链表的头节点Head；
2、让快指针fast一次向后移动两个节点，慢指针一次向后移动一个节点；
3、判断fast和slow是否移动到同一个节点上，如果移动到同一个节点上，就返回true；如果还没有移动到同一个节点上，进行步骤二。
4、上几个步骤通过循环完成，循环的结束条件是fast或者fast->next指向NULL.

分析问题

但是我们有以下问题：
1、为什么循环的结束条件是fast或者fast->next指向NULL？

如果一个链表中有环时，fast和fast->next永远不会指向NULL
如果一个链表中没有环时，fast一定会移动到链表的结尾；又因为fast一次移动两个节点，所以有两种情况：
- ①fast移动两次后，刚好指向NULL，结束循环；
- ②fast移动一次后就已经指向NULL，此时再进行移动，就会出现对NULL的解引用。

2、为什么要求快指针fast一次移动两个节点，慢指针slow一次移动一个节点？

我们先总结一下移动中的三种情况：

1）快指针fast和慢指针slow都没有进入环的入口点
在这里插入图片描述
2）快指针fast进入环的入口点（或已在环内）;慢指针slow没有进入环的入口点:

3）快指针fast和慢指针slow都在环内:

在这里插入图片描述
我们将这个链表抽象成一个数学模型：

我们假设这个链表是环形链表，当slow刚刚到达环的入口点，由于fast比slow快，所以此时fast一定在环内；
我们看成fast在后面追赶slow，设此时fast距离slow为N；
向后移动一次（slow移动一个节点，fast移动两个节点）后，fast与slow的距离就减小到N-1；
在这里插入图片描述
依次下去，fast与slow之间的距离：N-1-1-1-1-1…;直到N会被减小到零，两者就相遇了。

3、fast一次不能移动三个/四个节点吗？
移动三个节点
同理：此时fast和slow的距离设为N，当fast和slow每次移动时，两者的距离就会变成N-2，所以N-2-2-2-2…;
所以，只有N为2的倍数才能然fast与slow相遇；

移动四个节点也是如此；

代码展示

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
    ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast -> next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}