Linked List Cycle II - Practice Coding Problems

Linked List Cycle II - Problem

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Input & Output

Example 1 — Cycle Exists

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

› Output: Node with value 2

💡 Note: The cycle begins at node with value 2 (index 1). The last node (-4) points back to the node with value 2.

Example 2 — Self Loop

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

› Output: Node with value 1

💡 Note: The cycle begins at the head node (value 1). The second node points back to the first node.

Example 3 — No Cycle

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

› Output: null

💡 Note: There is only one node and no cycle exists, so return null.

Constraints

The number of the 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 with potential cycle

Process

Detect cycle and find starting point

Output

Return the cycle start node or null

Key Takeaway

🎯 Key Insight: Floyd's algorithm mathematically guarantees that after detecting a cycle, resetting one pointer to head and moving both at same speed will make them meet exactly at the cycle start.

Asked in

f Facebook 45 a Amazon 38 M Microsoft 32 G Google 28

The key insight is using Floyd's cycle detection algorithm. Phase 1: Use fast/slow pointers to detect if cycle exists. Phase 2: Reset one pointer to head and move both at same speed until they meet at cycle start. Best approach is Floyd's algorithm with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Tracking	O(n)	O(n)	Store all visited nodes in a set until we find a duplicate
Floyd's Cycle Detection	O(n)	O(1)	Use fast and slow pointers to detect cycle, then find the starting point

Hash Set Tracking — Algorithm Steps

Step 1: Create empty hash set
Step 2: Traverse list, adding each node to set
Step 3: If node already exists in set, return it
Step 4: If we reach null, return null

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create empty hash set and start from head

Traverse

Visit each node, adding to set

Detect

When we find a node already in set, that's the cycle start

Code -

solution.c — C

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

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

struct ListNode* solution(struct ListNode* head) {
    if (!head || !head->next) return NULL;
    
    // Use array to track visited nodes (simple implementation)
    struct ListNode* visited[1000];
    int visitedCount = 0;
    struct ListNode* current = head;
    
    while (current) {
        for (int i = 0; i < visitedCount; i++) {
            if (visited[i] == current) {
                return current;
            }
        }
        visited[visitedCount++] = current;
        current = current->next;
    }
    
    return NULL;
}

struct ListNode* arrayToList(int* arr, int size) {
    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];
    }
    struct ListNode* head = nodes[0];
    free(nodes);
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && size < 100) {
            arr[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    if (result) {
        printf("[%d]\n", result->val);
    } else {
        printf("null\n");
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once until cycle is found

✓ Linear Growth

Space Complexity

O(n)

Hash set stores up to n nodes in worst case

⚡ Linearithmic Space

180.0K Views

High Frequency

~25 min Avg. Time

8.5K 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

Hash Set Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler