Linked List Cycle Detection

NeetCode: Linked List Cycle Detection · LeetCode: 141. Linked List Cycle Detection · Difficulty: Easy

Return true if a linked list contains a cycle, meaning some node's next points back to an earlier node.

Example

Text

0 -> 1 -> 2 -> 3 -> back to 1    Output: true
0 -> 1 -> 2 -> 3 -> end          Output: false

Java linked structures use null and mutable fields, so the list is a chain of ListNode objects and the end of the list is next == null. LeetCode builds a cycle by pointing the last node's next at the node at index pos. The helper build(vals, pos) does the same: it links the values in order and, when pos >= 0, points the last node back to node pos.

Brute force: remember every visited node

Walk the list and record each node in a HashSet. ListNode does not override equals or hashCode, so the set compares nodes by identity, which is what the problem needs. Seeing a node a second time means a cycle.

Java

import java.util.HashSet;
import java.util.Set;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (!seen.add(cur)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
}

public class Main {
    static ListNode build(int[] vals, int pos) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode target = null;
        for (int i = 0; i < vals.length; i++) {
            tail.next = new ListNode(vals[i]);
            tail = tail.next;
            if (i == pos) {
                target = tail;
            }
        }
        if (pos >= 0) {
            tail.next = target;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.hasCycle(build(new int[]{0, 1, 2, 3}, 1)));
        System.out.println(s.hasCycle(build(new int[]{0, 1, 2, 3}, -1)));
    }
}

Output

true
false

Time: O(n). Space: O(n).

Optimal: Floyd's tortoise and hare

Move a slow pointer one step and a fast pointer two steps at a time. Without a cycle, fast reaches null. With a cycle, both end up circling inside it, and because fast gains one step on slow every round, it eventually lands exactly on slow.

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

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

public class Main {
    static ListNode build(int[] vals, int pos) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode target = null;
        for (int i = 0; i < vals.length; i++) {
            tail.next = new ListNode(vals[i]);
            tail = tail.next;
            if (i == pos) {
                target = tail;
            }
        }
        if (pos >= 0) {
            tail.next = target;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.hasCycle(build(new int[]{0, 1, 2, 3}, 1)));
        System.out.println(s.hasCycle(build(new int[]{0, 1, 2, 3}, -1)));
        System.out.println(s.hasCycle(build(new int[]{}, -1)));
    }
}

Output

true
false
false

The loop checks fast.next != null before reading fast.next.next, so an empty list, a one-node list, and an even-length list all stop without a NullPointerException.

Time: O(n). Space: O(1).