141.环形链表

发表于 更新于 分类于 ，

题目

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
img

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
img

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
img

思路

对于链表得环问题,我们可以使用快慢指针来解决.

想象两个人在环形跑道上同向跑步,一个快一个慢,那快的和慢的总会相遇的.我们利用这一个点,定义一个快指针,一个慢指针,如果它们两个相遇了,那说明链表有环.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public bool HasCycle(ListNode head)
{
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null)
    {
        fast = fast.next.next;//快指针每次走两步.
        slow = slow.next;//慢指针每次走一步.
        if (fast == slow)//两者相遇.
        {
            return true;
        }
    }
    return false;
}