141. 环形链表

xkrivzooh2023年2月28日
大约 1 分钟

141. 环形链表

题目:

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

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

如果链表中存在环,则返回 true 。 否则,返回 false 。

leetcode地址:https://leetcode.cn/problems/linked-list-cycleopen in new window

思路

要使用双指针技巧中的快慢指针,每当慢指针 slow 前进一步,快指针 fast 就前进两步。

如果 fast 最终遇到空指针,说明链表中没有环;如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow 一圈,说明链表中含有环。

solution

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 快慢指针初始化指向 head
        ListNode slow = head, fast = head;
        // 快指针走到末尾时停止
        while (fast != null && fast.next != null) {
            // 慢指针走一步,快指针走两步
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇,说明含有环
            if (slow == fast) {
                return true;
            }
        }
        // 不包含环
        return false;
    }
}
上次编辑于: 2023/2/28 15:05:37
Loading...