easyLinked List Essentials

Linked List Cycle

Build a linked list whose final node may point back to an earlier node. Determine whether the list contains a cycle.

LeetCode ↗

Work through the cases

3 examples

Input notation

List values on line 1; on line 2, the zero-based position the tail points to, or -1 for no cycle.

Expected result

true or false.

Case 1

Input

5 8 2
1

Expected output

true

Case 2

Input

1 2
-1

Expected output

false

Case 3

Input

5
0

Expected output

true

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Detect a cycle. n ≤ 10^4. Store visited nodes in a set; a repeat means a cycle, null means none. Simple, O(n) space. The follow-up asks for constant space.

We can traverse the linked list and use a hash table s to record each node. When a node appears for the second time, it indicates that there is a cycle, and we directly return true. Otherwise, when the linked list traversal ends, we return false.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the linked list.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> s = new HashSet<>();
        for (; head != null; head = head.next) {
            if (!s.add(head)) {
                return true;
            }
        }
        return false;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.