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

LeetCode100之环形链表(141)--Java

article 2024/11/17 15:43:15

1.问题描述

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

示例1

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

示例2

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

示例3

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

提示

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引

难度等级

简单

题目链接

环形链表

2.解题思路

这道环形链表的问题相当容易解决，有点像我们小学时候的追及问题。我们定义两个快慢指针来模拟两个人相互追及。

        //快指针
        ListNode fast = head;
        //慢指针
        ListNode slow = head;

如果链表真的是环形链表的话，它就会形成一个圈，那么我们的快慢指针相当于两个人从同一个入口进入一个闭环的操场在跑步。快的那个人只要时间足够，就可以比慢的那个人多跑一圈而相遇。

我们假设快指针的步频为2，慢指针步频为1，如果快指针能走到尽头，遇到null，说明不是环形链表，如果与慢指针相遇，说明是环形链表。

        //遍历
        while(fast != null && fast.next != null){
            //慢指针一次走一步
            slow = slow.next;
            //快指针一次走两步
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;

3.代码展示

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //快指针
        ListNode fast = head;
        //慢指针
        ListNode slow = head;
        //遍历
        while(fast != null && fast.next != null){
            //慢指针一次走一步
            slow = slow.next;
            //快指针一次走两步
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}