力扣hot100 环形链表 快慢指针 计步器

Problem: 141. 环形链表

思路

👨?🏫 参考题解

💖 快慢指针法

时间复杂度: $O(n)$
空间复杂度: $O(1)$

/**
 * 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)
	{
		int cnt = 0;
		ListNode slow = head;
		ListNode fast = head;
		while (fast != null)
		{
			fast = fast.next;
			if (fast != null)
				fast = fast.next;
			if (fast == slow)
				return true;
			slow = slow.next;
		}
		return false;
	}
}

💖 计步器法

时间复杂度: $O(n)$
空间复杂度: $O(1)$

/**
 * 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)
	{
        if(head == null)
            return false;
		int cnt = 0;
		while (cnt < 10000)
		{
			cnt++;
			if (head.next == null)
				return false;
			head = head.next;
		}
		return true;
	}
}