Problem: 141. 环形链表
题目描述
思路
定义快慢指针fast、slow,当fast != null && fast.next != null时fast每次走两步、slow走一步,当fast和slow相遇时,则说明存在环
复杂度
时间复杂度:
O ( n ) O(n) O(n)
空间复杂度:
O ( 1 ) O(1) O(1)
Code
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
/**
* Linked List Cycle
*
* @param head The head of linked list
* @return boolean
*/
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
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;
}
}