Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Subscribeto see which companies asked this question.

Hide Tags

Linked List

Two Pointers

Hide Similar Problems

(M) Linked List Cycle II

public boolean hasCycle(ListNode head) {
    if(head==null) return false;
    ListNode walker = head;
    ListNode runner = head;
    while(runner.next!=null && runner.next.next!=null) {
        walker = walker.next;
        runner = runner.next.next;
        if(walker==runner) return true;
    }
    return false;
}

1. Use two pointers walker and runner

2. walker

moves step by step.

runner

moves two steps at time.

1. if the Linked List has a cycle walker and runner will meet at some

   point.