Linked List Cycle - Practice Coding Problems

Linked List Cycle - Problem

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Input & Output

Example 1 — Cycle Exists

$ Input: head = [3,2,0,-4], pos = 1

› Output: true

💡 Note: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed). The cycle is: 2 → 0 → -4 → back to 2.

Example 2 — Small Cycle

$ Input: head = [1,2], pos = 0

› Output: true

💡 Note: There is a cycle where the tail connects back to the 0th node. The cycle is: 1 → 2 → back to 1.

Example 3 — No Cycle

$ Input: head = [1], pos = -1

› Output: false

💡 Note: There is only one node and no cycle since pos = -1 indicates no connection back.

Constraints

The number of nodes in the list is in the range [0, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵
pos is -1 or a valid index in the linked-list

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list that may or may not contain a cycle

Process

Use two pointers or hash set to detect revisited nodes

Output

Return true if cycle exists, false otherwise

Key Takeaway

🎯 Key Insight: Use two pointers at different speeds - if there's a cycle, the fast pointer will eventually meet the slow one

Asked in

A Amazon 42 M Microsoft 38 🍎 Apple 35 G Google 31

The key insight is that in a cycle, a fast-moving pointer will eventually catch a slow-moving pointer. The optimal approach uses Floyd's Cycle Detection Algorithm with two pointers moving at different speeds. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers (Floyd's Algorithm)	O(n)	O(1)	Use fast and slow pointers - they meet if there's a cycle
Hash Set (Visited Nodes)	O(n)	O(n)	Track all visited nodes in a set to detect revisits

Two Pointers (Floyd's Algorithm) — Algorithm Steps

Step 1: Initialize slow and fast pointers at head
Step 2: Move slow by 1 step, fast by 2 steps
Step 3: If they meet, cycle exists
Step 4: If fast reaches null, no cycle

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Both pointers start at head

Move

Slow moves 1 step, fast moves 2 steps

Meet

If cycle exists, pointers will meet inside cycle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

bool solution(struct ListNode* head) {
    if (!head || !head->next) {
        return false;
    }
    
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

struct ListNode* arrayToLinkedList(int* arr, int size, int pos) {
    if (size == 0) return NULL;
    
    struct ListNode** nodes = malloc(size * sizeof(struct ListNode*));
    for (int i = 0; i < size; i++) {
        nodes[i] = malloc(sizeof(struct ListNode));
        nodes[i]->val = arr[i];
        nodes[i]->next = NULL;
    }
    
    for (int i = 0; i < size - 1; i++) {
        nodes[i]->next = nodes[i + 1];
    }
    
    if (pos != -1) {
        nodes[size - 1]->next = nodes[pos];
    }
    
    struct ListNode* head = nodes[0];
    free(nodes);
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] or [[1,2,3],1]
    int arr[100];
    int size = 0;
    int pos = -1;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* endPtr = strchr(ptr, ']');
        if (endPtr) {
            *endPtr = '\0';
            char* token = strtok(ptr, ",");
            while (token && size < 100) {
                arr[size++] = atoi(token);
                token = strtok(NULL, ",");
            }
        }
    }
    
    struct ListNode* head = arrayToLinkedList(arr, size, pos);
    bool result = solution(head);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, traverse the list once plus cycle length

✓ Linear Growth

Space Complexity

O(1)

Only uses two pointer variables

✓ Linear Space

321.1K Views

High Frequency

~15 min Avg. Time

8.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers (Floyd's Algorithm) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler