Given a linked list, determine if it has a cycle in it. Can you solve it without using extra space?

/*
Definition for singly-linked list.

public class Node {
  int val;
  Node next;
  Node(int x) { val = x; }
}
*/

public class Solution {
  public boolean hasCycle(Node l1) {
  	
  }
}

This problem is selected from LeetCode.

Solution

Setup a fast pointer and a slow pointer. When the fast pointer meets the slow pointer, that means the linked list has a cycle.
If the fast pointer reaches the tail (null), then it does not have cycles.

public class Solution {
  public boolean hasCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
  
    while(fast!=null) {
      
      fast = fast.next;
      if(fast==null) 
        break;
        
      fast = fast.next;
      if(fast==null) 
        break;
      
      slow = slow.next;
      
      if(fast==slow) 
        return true;
    }
    
    return false; 
  }
}

RelatedPost