Leetcode: Given a list, find whether cycle is present in the list.


https://leetcode.com/problems/linked-list-cycle

Consider example 1->2->3->4->1 List has cycle.

Consider example 1->2->3->4 List doesn't have cycle.

The problem can be solved by having slow and fast pointer. Increment slow pointer once and increment fast pointer twice. Check whether the node at slow and fast pointer is same. If the value is same, return true or continue unless end of list is present.

The LinkedList for the example is singly. Here is how Node class looks like:

class Node {
	int value;
	protected Node next;
	
	public Node(int value) {
		this.value = value;
	}
	
	public int getValue() {
		return value;
	}
}

public class LinkedListCycle {

	public boolean hasCycle(Node head) {
        if(head==null) return false;
		Node slow = head;
		Node fast = head;
		while(slow.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			if(slow == fast) return true;
		}
		return false;
    }
}	

Subscribe to get latest updates.

© 2016 Java Questions | Sitemap