Linked List Cycle Length

🎯

Linked List Cycle Length

easyTWO_POINTERAmazonGoogle

Imagine you are debugging a network of pipes and want to find if water flows in a loop, and if so, how long that loop is.

💡 This problem involves detecting a cycle in a linked list and then measuring its length. Beginners often struggle because they don't know how to detect cycles efficiently or how to count the cycle length once detected. Understanding the fast and slow pointer technique is key.

📋

Problem Statement

Given the head of a singly linked list, determine if the linked list contains a cycle. If a cycle exists, return the length of the cycle (the number of nodes in the cycle). If there is no cycle, return 0.

The number of nodes in the list is in the range [0, 10^5].Node values can be any integer.You must solve the problem using O(1) additional space.

💡

Example

Input"head = [3,2,0,-4], where the tail connects to the node at position 1 (0-indexed)"

Output3

The cycle is formed by nodes with values 2 -> 0 -> -4 -> back to 2, so the cycle length is 3.

Input"head = [1,2], where the tail connects to the node at position 0"

Output2

The cycle includes nodes 1 and 2, so the length is 2.

Input"head = [1], no cycle"

Output0

No cycle exists, so the output is 0.

• Empty list (head = null) → 0
• Single node with no cycle → 0
• Single node with cycle to itself → 1
• Cycle at the very end of the list → length of cycle
• Long list with no cycle → 0

⚠️

Common Mistakes

Not checking if fast and fast.next are null before advancing fast pointer

Runtime error due to null pointer dereference

✅ Always check fast and fast.next are not null before moving fast pointer

Counting cycle length incorrectly by moving the wrong pointer or off-by-one errors

Incorrect cycle length returned

✅ After detecting cycle, move one pointer step by step until it meets the other pointer again, counting steps carefully

Using extra space when the problem expects O(1) space

Suboptimal solution that may be rejected in interviews

✅ Use fast and slow pointer technique instead of hash sets

Not handling edge cases like empty list or single node with cycle

Incorrect output or runtime errors

✅ Add explicit checks for empty list and single node cases

🧠

Brute Force (Hash Set to Detect Cycle and Count Length)

💡 This approach uses extra memory to store visited nodes. It is straightforward and helps beginners understand cycle detection by explicitly tracking visited nodes, but it is not optimal in space.

Intuition

Traverse the linked list and store each visited node in a hash set. When a node repeats, a cycle is detected. Then, count the number of nodes in the cycle by traversing from the repeated node until you come back to it.

Algorithm

1. Initialize an empty hash set to store visited nodes.
2. Traverse the linked list node by node.
3. If the current node is already in the set, a cycle is detected; break.
4. If no cycle is detected, return 0.
5. If a cycle is detected, start from the repeated node and count nodes until you return to it to find the cycle length.

💡 This algorithm is easy to follow but requires extra memory, which is not ideal for large lists.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            # Cycle detected, count length
            length = 1
            node = current.next
            while node != current:
                length += 1
                node = node.next
            return length
        visited.add(current)
        current = current.next
    return 0

# Example usage:
if __name__ == '__main__':
    # Create a cycle list: 3->2->0->-4->2...
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # cycle here
    print(cycle_length(node1))  # Output: 3

Line Notes

visited = set()Initialize a set to keep track of visited nodes to detect repeats.

while current:Traverse the linked list until the end or a cycle is found.

if current in visited:Check if current node was seen before, indicating a cycle.

while node != current:Count nodes in the cycle by looping until we return to the start node.

import java.util.HashSet;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public static int cycleLength(ListNode head) {
        HashSet<ListNode> visited = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visited.contains(current)) {
                int length = 1;
                ListNode node = current.next;
                while (node != current) {
                    length++;
                    node = node.next;
                }
                return length;
            }
            visited.add(current);
            current = current.next;
        }
        return 0;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // cycle
        System.out.println(cycleLength(node1)); // Output: 3
    }
}

Line Notes

HashSet<ListNode> visited = new HashSet<>();Use a hash set to track visited nodes for cycle detection.

while (current != null)Traverse the linked list until the end or cycle found.

if (visited.contains(current))Detect cycle when a node is revisited.

while (node != current)Count the cycle length by iterating until back to start node.

#include <iostream>
#include <unordered_set>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int cycleLength(ListNode* head) {
    unordered_set<ListNode*> visited;
    ListNode* current = head;
    while (current != nullptr) {
        if (visited.find(current) != visited.end()) {
            int length = 1;
            ListNode* node = current->next;
            while (node != current) {
                length++;
                node = node->next;
            }
            return length;
        }
        visited.insert(current);
        current = current->next;
    }
    return 0;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2; // cycle
    cout << cycleLength(node1) << endl; // Output: 3
    return 0;
}

Line Notes

unordered_set<ListNode*> visited;Use unordered_set to store visited nodes for O(1) lookup.

while (current != nullptr)Traverse nodes until end or cycle detected.

if (visited.find(current) != visited.end())Detect cycle by checking if node was visited before.

while (node != current)Count cycle length by iterating until back to start node.

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function cycleLength(head) {
    const visited = new Set();
    let current = head;
    while (current !== null) {
        if (visited.has(current)) {
            let length = 1;
            let node = current.next;
            while (node !== current) {
                length++;
                node = node.next;
            }
            return length;
        }
        visited.add(current);
        current = current.next;
    }
    return 0;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // cycle
console.log(cycleLength(node1)); // Output: 3

Line Notes

const visited = new Set();Create a set to track visited nodes for cycle detection.

while (current !== null)Traverse the linked list until no more nodes or cycle found.

if (visited.has(current))Detect cycle when a node is revisited.

while (node !== current)Count the cycle length by looping until back to start node.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse each node once and store each in a hash set, so time is linear. Space is linear due to the hash set storing nodes.

💡 For n=100,000 nodes, this means up to 100,000 insertions and lookups in the set, which is feasible but uses extra memory.

Interview Verdict: Accepted but not optimal due to extra space

This approach works but uses extra memory, which is not ideal for large inputs or interviews expecting O(1) space.

🧠

Fast and Slow Pointer to Detect Cycle, Then Count Length

💡 This approach uses two pointers moving at different speeds to detect a cycle without extra space. It is a classic technique that is efficient and commonly expected in interviews.

Intuition

Use two pointers: slow moves one step at a time, fast moves two steps. If they meet, a cycle exists. Then, to find the cycle length, keep one pointer fixed and move the other until it meets again, counting steps.

Algorithm

1. Initialize two pointers, slow and fast, at the head.
2. Move slow by one step and fast by two steps until they meet or fast reaches the end.
3. If no meeting point, return 0 (no cycle).
4. If they meet, keep slow fixed and move fast one step at a time, counting steps until fast meets slow again.
5. Return the count as the cycle length.

💡 This algorithm cleverly uses pointer speeds to detect cycles and then counts cycle length efficiently.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Cycle detected, count length
            length = 1
            fast = fast.next
            while fast != slow:
                length += 1
                fast = fast.next
            return length
    return 0

# Example usage:
if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2
    print(cycle_length(node1))  # Output: 3

Line Notes

slow = fast = headInitialize both pointers at the start of the list.

while fast and fast.next:Ensure fast pointer and its next node exist to avoid null errors.

if slow == fast:Pointers meet means a cycle is detected.

while fast != slow:Count cycle length by moving fast until it meets slow again.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public static int cycleLength(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                int length = 1;
                fast = fast.next;
                while (fast != slow) {
                    length++;
                    fast = fast.next;
                }
                return length;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(cycleLength(node1)); // Output: 3
    }
}

Line Notes

ListNode slow = head, fast = head;Initialize slow and fast pointers at the head.

while (fast != null && fast.next != null)Check fast pointer and next to avoid null pointer exceptions.

if (slow == fast)Detect cycle when pointers meet.

while (fast != slow)Count cycle length by moving fast until it meets slow again.

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int cycleLength(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            int length = 1;
            fast = fast->next;
            while (fast != slow) {
                length++;
                fast = fast->next;
            }
            return length;
        }
    }
    return 0;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;
    cout << cycleLength(node1) << endl; // Output: 3
    return 0;
}

Line Notes

ListNode* slow = head;Initialize slow pointer at head.

while (fast && fast->next)Ensure fast pointer and next exist to avoid null dereference.

if (slow == fast)Cycle detected when pointers meet.

while (fast != slow)Count cycle length by moving fast until it meets slow.

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function cycleLength(head) {
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let length = 1;
            fast = fast.next;
            while (fast !== slow) {
                length++;
                fast = fast.next;
            }
            return length;
        }
    }
    return 0;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;
console.log(cycleLength(node1)); // Output: 3

Line Notes

let slow = head, fast = head;Initialize two pointers at the start.

while (fast !== null && fast.next !== null)Check pointers to avoid null errors.

if (slow === fast)Detect cycle when pointers meet.

while (fast !== slow)Count cycle length by moving fast until it meets slow.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited at most a constant number of times by the pointers, so time is linear. Space is constant as no extra data structures are used.

💡 For n=100,000 nodes, this means about 100,000 steps, which is efficient and uses minimal memory.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and constant space usage.

🧠

Optimized Fast-Slow Pointer with Early Exit and Cycle Length Counting

💡 This approach is a slight optimization of the classic fast-slow pointer method, adding early exit checks and clearer cycle length counting logic to improve readability and efficiency.

Intuition

Detect cycle with fast and slow pointers. Once detected, move one pointer step by step counting nodes until it meets the other pointer again to find cycle length. Early exit if no cycle.

Algorithm

1. Initialize slow and fast pointers at head.
2. Move slow by one and fast by two steps until they meet or fast reaches null.
3. If no meeting, return 0.
4. Set a counter to 1 and move slow one step at a time until it meets fast again, incrementing counter.
5. Return the counter as the cycle length.

💡 This approach emphasizes clarity and early termination to avoid unnecessary iterations.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    if not head:
        return 0
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            length = 1
            slow = slow.next
            while slow != fast:
                length += 1
                slow = slow.next
            return length
    return 0

# Example usage:
if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2
    print(cycle_length(node1))  # Output: 3

Line Notes

if not head:Handle empty list edge case immediately.

while fast and fast.next:Ensure pointers are valid to avoid errors.

if slow == fast:Detect cycle when pointers meet.

while slow != fast:Count cycle length by moving slow until it meets fast again.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public static int cycleLength(ListNode head) {
        if (head == null) return 0;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                int length = 1;
                slow = slow.next;
                while (slow != fast) {
                    length++;
                    slow = slow.next;
                }
                return length;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(cycleLength(node1)); // Output: 3
    }
}

Line Notes

if (head == null) return 0;Handle empty list early to avoid unnecessary processing.

while (fast != null && fast.next != null)Check pointers to prevent null pointer exceptions.

if (slow == fast)Cycle detected when pointers meet.

while (slow != fast)Count cycle length by moving slow until it meets fast.

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int cycleLength(ListNode* head) {
    if (!head) return 0;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            int length = 1;
            slow = slow->next;
            while (slow != fast) {
                length++;
                slow = slow->next;
            }
            return length;
        }
    }
    return 0;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;
    cout << cycleLength(node1) << endl; // Output: 3
    return 0;
}

Line Notes

if (!head) return 0;Return immediately if list is empty.

while (fast && fast->next)Check pointers to avoid null dereference.

if (slow == fast)Detect cycle when pointers meet.

while (slow != fast)Count cycle length by moving slow until it meets fast.

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function cycleLength(head) {
    if (!head) return 0;
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let length = 1;
            slow = slow.next;
            while (slow !== fast) {
                length++;
                slow = slow.next;
            }
            return length;
        }
    }
    return 0;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;
console.log(cycleLength(node1)); // Output: 3

Line Notes

if (!head) return 0;Handle empty list edge case immediately.

while (fast !== null && fast.next !== null)Check pointers to avoid runtime errors.

if (slow === fast)Detect cycle when pointers meet.

while (slow !== fast)Count cycle length by moving slow until it meets fast.

⏱

Complexity

TimeO(n)

SpaceO(1)

The algorithm visits each node a constant number of times, so time is linear. Space is constant as no extra data structures are used.

💡 This approach is efficient for large inputs and uses minimal memory, ideal for interviews.

Interview Verdict: Accepted and optimal with minor improvements

This approach is a polished version of the classic fast-slow pointer method, showing good coding style and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the fast and slow pointer approach (Approach 2 or 3) is the best to code due to its optimal time and space. The brute force approach is useful to mention but not to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Hash Set)	O(n)	O(n)	No	Yes	Mention only - never code
2. Fast and Slow Pointer	O(n)	O(1)	No	Yes	Code this approach
3. Optimized Fast-Slow Pointer	O(n)	O(1)	No	Yes	Code this approach if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, followed by the optimal fast-slow pointer method. Practice coding and testing edge cases.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach using a hash set to detect cycles.Explain its drawbacks (extra space) and introduce the fast and slow pointer technique.Detail how to detect the cycle and count its length using pointers.Write clean, tested code and discuss edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of cycle detection, pointer manipulation, and ability to optimize space. They also check your handling of edge cases and code correctness.

Common Follow-ups

• What if you need to find the node where the cycle begins? → Use fast-slow pointers and reset one pointer to head, move both one step until they meet.
• Can you detect cycle length without counting nodes explicitly? → No, counting nodes in the cycle requires traversal.

💡 These follow-ups test deeper understanding of cycle detection and pointer techniques.

🔍

Pattern Recognition

When to Use

1) Problem involves linked list or sequence traversal; 2) Need to detect cycles or loops; 3) Constraints require O(1) space; 4) Counting or detecting repeated nodes.

Signature Phrases

detect cycle in linked listfind length of cyclefast and slow pointers

NOT This Pattern When

Problems that require reversing linked lists or sorting arrays are different patterns.

Similar Problems

Linked List Cycle Detection - detect if cycle existsHappy Number - detect cycle in number sequenceFind the Duplicate Number - detect cycle in array indices

Practice

1. Given the following code snippet for detecting a circular array loop, what is the return value when the input is nums = [2, -1, 1, 2, 2]?

easy

A. True

B. False

C. Raises an IndexError

D. Infinite loop

Solution

1. Step 1: Trace first iteration starting at index 0

   nums[0]=2 (positive), direction is forward. slow and fast start at 0.

2. Step 2: Move slow and fast pointers

   slow moves to index (0+2)%5=2, fast moves two steps: first to 2, then to (2+1)%5=3. Both nums[2] and nums[3] are positive, direction consistent.

3. Step 3: Next iteration

   slow moves to (2+1)%5=3, fast moves two steps: from 3 to (3+2)%5=0, then from 0 to (0+2)%5=2. slow=3, fast=2, not equal yet.

4. Step 4: Next iteration

   slow moves to (3+2)%5=0, fast moves two steps: from 2 to (2+1)%5=3, then from 3 to (3+2)%5=0. slow=0, fast=0, pointers meet.

5. Step 5: Check cycle length

   Check if slow == next_index(slow): next_index(0) = 2, not equal, so cycle length > 1.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Cycle detected with consistent direction and length > 1 [OK]

Hint: Pointers meet at index 0 with valid cycle -> returns True [OK]

Common Mistakes:

• Confusing slow and fast pointer positions
• Ignoring direction check
• Mistaking single-element loop as valid

2. Consider the following Python code that removes the 2nd node from the end of the list 1 -> 2 -> 3 -> 4 -> 5. What is the printed output after execution?

easy

A. 1 2 4 5

B. 1 2 3 5

C. 1 3 4 5

D. 2 3 4 5

Solution

1. Step 1: Trace recursion from end

   Recursion returns indices from the end: node 5 returns 1, node 4 returns 2, node 3 returns 3, etc.

2. Step 2: Identify node to remove

   When idx == n+1 = 3, node 3's next pointer skips node 4, effectively removing node 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches list with 4 removed: 1 2 3 5 [OK]

Hint: Recursion index counts from end; remove node at idx = n+1 [OK]

Common Mistakes:

• Removing the node at idx == n instead of n+1
• Off-by-one errors in recursion index
• Confusing which node to skip

3. What is the time complexity of the optimal Happy Number detection algorithm that uses a known cycle set and repeatedly computes the sum of squares of digits until it reaches 1 or a cycle number? Assume n is the input number and k is the number of iterations until termination.

medium

A. O(n) because each digit is processed once per iteration

B. O(k * log n) because each iteration processes digits proportional to log n and there are k iterations

C. O(k * n) because sum of squares depends on n itself

D. O(k) because the cycle detection set lookup is constant time and digits are fixed length

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits. Number of digits in n is proportional to log n, so each iteration is O(log n).

2. Step 2: Multiply by number of iterations k

   The process repeats k times until reaching 1 or cycle. Total time is O(k * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of digits per iteration is log n, repeated k times -> O(k * log n) [OK]

Hint: Sum of digits cost is O(log n), not O(n) [OK]

Common Mistakes:

• Confusing n with number of digits, assuming O(n) per iteration

4. Consider the following buggy code snippet for reorderList. Which line contains the subtle bug that can cause infinite loops or cycles when traversing the reordered list?

medium

A. Line with 'if left == right or left.next == right:' missing 'right.next = None' termination

B. Line with 'if not right: return' -- base case missing

C. Line with 'if stop: return' -- premature termination

D. Line with 'left = tmp' -- left pointer not updated correctly

Solution

1. Step 1: Identify termination condition

   The code must set right.next = None when left meets right or adjacent to avoid cycles.

2. Step 2: Locate missing termination

   The commented line misses 'right.next = None', causing the list to form cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing termination causes infinite traversal [OK]

Hint: Always terminate reordered list with null to avoid cycles [OK]

Common Mistakes:

• Forgetting to set right.next = null
• Misplacing stop flag
• Incorrect pointer updates

5. What is the time complexity of the optimal one-pass splitting algorithm for splitting a linked list of length n into k parts, and why?

medium

A. O(n + k) because we first count nodes in O(n) and then split in O(k) steps.

B. O(n * k) because for each of the k parts, we traverse nodes up to part size.

C. O(n) because we only traverse the list once without extra passes.

D. O(k) because we only create k parts and do constant work per part.

Solution

1. Step 1: Analyze counting nodes

   Counting total nodes requires traversing the entire list once -> O(n).

2. Step 2: Analyze splitting parts

   Splitting involves iterating over k parts and moving pointers, total steps sum to n nodes plus k iterations -> O(n + k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting + splitting both contribute; total is O(n + k) [OK]

Hint: Counting nodes plus splitting parts sums to O(n + k) [OK]

Common Mistakes:

• Assuming O(n*k) due to nested loops
• Ignoring counting step
• Confusing k with n