Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 141] Linked List Cycle



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

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


Adjusted Difficulty 4
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)


This is an famous question, historically know as the Tortoise and hare.


This blog has a great solution.

Use fast and low pointer. The advantage about fast/slow pointers is that when a circle is located, the fast one will catch the slow one for sure.


public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) 
        return false;
    ListNode first = head.next, second = first.next;
    while (first != null && second != null) {
        if (first == second) return true;
        first = first.next;
        second = second.next;
        if (second == null) return false;
        second = second.next;
    return false;