[链表OJ题 7] 环形链表

亦凉 2023-09-27 23:38 34阅读 0赞

**目录**

题目来源：

代码实现：

思路分析：

实现过程：

--------------------

## 题目来源： ##

[力扣 141. 环形链表][141.]

**题目描述**

![209d22a0f3fb72f09b467f32f9d22f16.png][]

## 代码实现： ##

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;
    }

## 思路分析： ##

本题是要看链表是否成环，那我们就定义快、慢两个指针，快指针一次走两步，慢指针一次走一步。如果链表是成环的，快指针一定就可以追赶上慢指针，重合后就是成环的；如果链表不成环，那我们的快指针就会走到空。

![d518553b5ff5b97ae6180d7cc5f9bfbe.png][]

![f64d15530d589fe47c9673077ffb7132.png][]

### 实现过程： ###

1、使用快慢指针，初始化都指向原链表的头，慢指针一次走一步，快指针一次走两步；

2、在循环的时候我们加上一条判断语句，fast == slow 时，就说明链表是成环的；

3、如果快指针走到了空，或者快指针的 next 为空时，那就说明链表是不成环的。

![b92a618df08678801f7f0d5b14f90e60.png][]

![760fde69be2841adc9f35967fbb6e9ad.png][]

\*\*\* 本篇结束 \*\*\*

[141.]: https://leetcode.cn/problems/linked-list-cycle/
[209d22a0f3fb72f09b467f32f9d22f16.png]: https://img-blog.csdnimg.cn/img_convert/209d22a0f3fb72f09b467f32f9d22f16.png
[d518553b5ff5b97ae6180d7cc5f9bfbe.png]: https://img-blog.csdnimg.cn/img_convert/d518553b5ff5b97ae6180d7cc5f9bfbe.png
[f64d15530d589fe47c9673077ffb7132.png]: https://img-blog.csdnimg.cn/img_convert/f64d15530d589fe47c9673077ffb7132.png
[b92a618df08678801f7f0d5b14f90e60.png]: https://img-blog.csdnimg.cn/img_convert/b92a618df08678801f7f0d5b14f90e60.png
[760fde69be2841adc9f35967fbb6e9ad.png]: https://img-blog.csdnimg.cn/img_convert/760fde69be2841adc9f35967fbb6e9ad.png