Delete N Nodes After M Nodes

🎯

Delete N Nodes After M Nodes

mediumTWO_POINTERAmazonGoogle

Imagine you are managing a playlist and want to skip a few songs after listening to some, deleting the skipped ones permanently.

💡 This problem involves linked list manipulation using pointers to skip and delete nodes. Beginners often struggle with pointer updates and edge cases like deleting at the end or when the list is shorter than expected.

📋

Problem Statement

Given the head of a singly linked list and two integers M and N, traverse the list such that you retain M nodes, then delete the next N nodes, and continue this pattern until the end of the list. Return the head of the modified list.

The number of nodes in the list is in the range [1, 10^5]1 ≤ M, N ≤ 10^5The list may be shorter than M or N at any point

💡

Example

Input"head = [1,2,3,4,5,6,7,8,9,10], M = 2, N = 3"

Output[1,2,6,7]

Keep first 2 nodes (1,2), delete next 3 nodes (3,4,5), keep next 2 nodes (6,7), delete next 3 nodes (8,9,10).

• List length less than M → entire list remains
• List length less than M + N → delete only available N nodes after M
• M = 0 → delete all nodes
• N = 0 → no nodes deleted, list remains unchanged

⚠️

Common Mistakes

Not checking for null before moving pointers

Runtime error or segmentation fault

✅ Add null checks before pointer dereferences

Incorrectly updating next pointers causing cycles or lost nodes

Infinite loops or missing nodes in output

✅ Ensure current.next points to the correct node after deletion

Deleting nodes without freeing memory in languages like C++

Memory leaks

✅ Explicitly delete nodes when removing them

Not handling edge cases where M or N is zero

Incorrect output or infinite loops

✅ Add explicit checks for zero values and handle accordingly

Using recursion without considering stack overflow

Stack overflow on large inputs

✅ Prefer iterative approach for large lists

🧠

Brute Force (Iterative with Nested Loops)

💡 This approach uses straightforward iteration to simulate the problem exactly as stated, helping beginners understand the mechanics of skipping and deleting nodes step-by-step.

Intuition

Traverse the list, skip M nodes by moving a pointer forward, then delete N nodes by adjusting pointers to bypass them, repeating until the list ends.

Algorithm

1. Initialize a pointer at the head.
2. Skip M nodes by moving the pointer forward M times.
3. From the current pointer, delete the next N nodes by adjusting the next pointer.
4. Repeat the process until the end of the list is reached.

💡 This method is easy to visualize but requires careful pointer updates to avoid losing parts of the list or causing cycles.

</>

Code

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

def delete_n_after_m(head, M, N):
    current = head
    while current:
        # Skip M nodes
        for _ in range(1, M):
            if current is None:
                return head
            current = current.next
        if current is None:
            return head
        # Delete N nodes
        temp = current.next
        for _ in range(N):
            if temp is None:
                break
            temp = temp.next
        current.next = temp
        current = temp
    return head

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->2->3->4->5->6->7->8->9->10
    nodes = [ListNode(i) for i in range(1, 11)]
    for i in range(9):
        nodes[i].next = nodes[i+1]
    head = nodes[0]
    M, N = 2, 3
    new_head = delete_n_after_m(head, M, N)
    # Print result
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1, 2, 6, 7]

Line Notes

current = headStart traversal from the head of the list

for _ in range(1, M)Skip M nodes by moving current pointer forward M-1 times

if current is None:Check if reached end while skipping to avoid errors

temp = current.nextStart deleting nodes from the node after current

for _ in range(N)Delete N nodes by moving temp pointer forward N times

current.next = tempLink current node to the node after deleted nodes

current = tempMove current pointer to continue process

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

public class Solution {
    public static ListNode deleteNAfterM(ListNode head, int M, int N) {
        ListNode current = head;
        while (current != null) {
            // Skip M nodes
            for (int i = 1; i < M && current != null; i++) {
                current = current.next;
            }
            if (current == null) return head;
            // Delete N nodes
            ListNode temp = current.next;
            for (int i = 0; i < N && temp != null; i++) {
                temp = temp.next;
            }
            current.next = temp;
            current = temp;
        }
        return head;
    }

    public static void main(String[] args) {
        // Create linked list 1->2->3->4->5->6->7->8->9->10
        ListNode head = new ListNode(1);
        ListNode curr = head;
        for (int i = 2; i <= 10; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        int M = 2, N = 3;
        ListNode newHead = deleteNAfterM(head, M, N);
        curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        // Expected output: 1 2 6 7
    }
}

Line Notes

ListNode current = head;Initialize pointer at head to start traversal

for (int i = 1; i < M && current != null; i++)Skip M nodes carefully checking for null

if (current == null) return head;If end reached while skipping, return early

ListNode temp = current.next;Start deleting nodes from next node

for (int i = 0; i < N && temp != null; i++)Move temp pointer N nodes ahead to delete

current.next = temp;Link current node to node after deleted nodes

current = temp;Move current pointer forward to continue

#include <iostream>
using namespace std;

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

ListNode* deleteNAfterM(ListNode* head, int M, int N) {
    ListNode* current = head;
    while (current) {
        // Skip M nodes
        for (int i = 1; i < M && current != nullptr; i++) {
            current = current->next;
        }
        if (current == nullptr) return head;
        // Delete N nodes
        ListNode* temp = current->next;
        for (int i = 0; i < N && temp != nullptr; i++) {
            ListNode* toDelete = temp;
            temp = temp->next;
            delete toDelete; // free memory
        }
        current->next = temp;
        current = temp;
    }
    return head;
}

int main() {
    // Create linked list 1->2->3->4->5->6->7->8->9->10
    ListNode* head = new ListNode(1);
    ListNode* curr = head;
    for (int i = 2; i <= 10; i++) {
        curr->next = new ListNode(i);
        curr = curr->next;
    }
    int M = 2, N = 3;
    head = deleteNAfterM(head, M, N);
    curr = head;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    // Expected output: 1 2 6 7
    return 0;
}

Line Notes

ListNode* current = head;Start traversal from head pointer

for (int i = 1; i < M && current != nullptr; i++)Skip M nodes carefully checking for null

if (current == nullptr) return head;Return early if end reached while skipping

ListNode* temp = current->next;Start deleting nodes from next node

delete toDelete;Free memory of deleted nodes to avoid leaks

current->next = temp;Link current node to node after deleted nodes

current = temp;Move current pointer forward to continue

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

function deleteNAfterM(head, M, N) {
    let current = head;
    while (current !== null) {
        // Skip M nodes
        for (let i = 1; i < M && current !== null; i++) {
            current = current.next;
        }
        if (current === null) return head;
        // Delete N nodes
        let temp = current.next;
        for (let i = 0; i < N && temp !== null; i++) {
            temp = temp.next;
        }
        current.next = temp;
        current = temp;
    }
    return head;
}

// Driver code
const nodes = [];
for (let i = 1; i <= 10; i++) {
    nodes.push(new ListNode(i));
}
for (let i = 0; i < 9; i++) {
    nodes[i].next = nodes[i + 1];
}
const M = 2, N = 3;
const newHead = deleteNAfterM(nodes[0], M, N);
let curr = newHead;
const res = [];
while (curr !== null) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1, 2, 6, 7]

Line Notes

let current = head;Initialize traversal pointer at head

for (let i = 1; i < M && current !== null; i++)Skip M nodes carefully checking for null

if (current === null) return head;Return early if end reached while skipping

let temp = current.next;Start deleting nodes from next node

for (let i = 0; i < N && temp !== null; i++)Move temp pointer N nodes ahead to delete

current.next = temp;Link current node to node after deleted nodes

current = temp;Move current pointer forward to continue

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list once, skipping M nodes and deleting N nodes repeatedly, so total operations proportional to n.

💡 For n=100,000 nodes, this means roughly 100,000 pointer moves and updates, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is efficient and accepted, making it a solid baseline solution.

🧠

Recursive Approach

💡 Recursion provides a clean, elegant way to think about the problem by handling one M+N segment at a time, but beginners must be careful with base cases and stack depth.

Intuition

Recursively skip M nodes, then delete N nodes by adjusting pointers, and call the function again on the remaining list.

Algorithm

1. Base case: if head is null, return null.
2. Skip M nodes by moving head pointer forward M-1 times.
3. Delete next N nodes by moving a temporary pointer forward N times.
4. Recursively call the function on the node after deleted nodes and link it back.

💡 Recursion breaks the problem into smaller identical subproblems, but requires careful pointer management.

</>

Code

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

def delete_n_after_m_recursive(head, M, N):
    if not head:
        return None
    current = head
    # Skip M nodes
    for _ in range(1, M):
        if current is None:
            return head
        current = current.next
    if current is None:
        return head
    # Delete N nodes
    temp = current.next
    for _ in range(N):
        if temp is None:
            break
        temp = temp.next
    current.next = delete_n_after_m_recursive(temp, M, N)
    return head

# Driver code
if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1, 11)]
    for i in range(9):
        nodes[i].next = nodes[i+1]
    head = nodes[0]
    M, N = 2, 3
    new_head = delete_n_after_m_recursive(head, M, N)
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1, 2, 6, 7]

Line Notes

if not head:Base case: empty list returns None

for _ in range(1, M):Skip M nodes by moving current pointer

if current is None:Check if end reached while skipping

for _ in range(N):Delete N nodes by moving temp pointer

current.next = delete_n_after_m_recursive(temp, M, N)Recursive call on remaining list after deletion

return headReturn modified list head

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

public class Solution {
    public static ListNode deleteNAfterMRecursive(ListNode head, int M, int N) {
        if (head == null) return null;
        ListNode current = head;
        // Skip M nodes
        for (int i = 1; i < M && current != null; i++) {
            current = current.next;
        }
        if (current == null) return head;
        // Delete N nodes
        ListNode temp = current.next;
        for (int i = 0; i < N && temp != null; i++) {
            temp = temp.next;
        }
        current.next = deleteNAfterMRecursive(temp, M, N);
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode curr = head;
        for (int i = 2; i <= 10; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        int M = 2, N = 3;
        ListNode newHead = deleteNAfterMRecursive(head, M, N);
        curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        // Expected output: 1 2 6 7
    }
}

Line Notes

if (head == null) return null;Base case for recursion termination

for (int i = 1; i < M && current != null; i++)Skip M nodes carefully

if (current == null) return head;Return if end reached while skipping

for (int i = 0; i < N && temp != null; i++)Move temp pointer N nodes ahead to delete

current.next = deleteNAfterMRecursive(temp, M, N);Recursive call on remaining list

return head;Return modified list head

#include <iostream>
using namespace std;

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

ListNode* deleteNAfterMRecursive(ListNode* head, int M, int N) {
    if (!head) return nullptr;
    ListNode* current = head;
    for (int i = 1; i < M && current != nullptr; i++) {
        current = current->next;
    }
    if (current == nullptr) return head;
    ListNode* temp = current->next;
    for (int i = 0; i < N && temp != nullptr; i++) {
        ListNode* toDelete = temp;
        temp = temp->next;
        delete toDelete;
    }
    current->next = deleteNAfterMRecursive(temp, M, N);
    return head;
}

int main() {
    ListNode* head = new ListNode(1);
    ListNode* curr = head;
    for (int i = 2; i <= 10; i++) {
        curr->next = new ListNode(i);
        curr = curr->next;
    }
    int M = 2, N = 3;
    head = deleteNAfterMRecursive(head, M, N);
    curr = head;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    // Expected output: 1 2 6 7
    return 0;
}

Line Notes

if (!head) return nullptr;Base case for recursion

for (int i = 1; i < M && current != nullptr; i++)Skip M nodes carefully

if (current == nullptr) return head;Return if end reached while skipping

delete toDelete;Free memory of deleted nodes

current->next = deleteNAfterMRecursive(temp, M, N);Recursive call on remaining list

return head;Return modified list head

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

function deleteNAfterMRecursive(head, M, N) {
    if (head === null) return null;
    let current = head;
    for (let i = 1; i < M && current !== null; i++) {
        current = current.next;
    }
    if (current === null) return head;
    let temp = current.next;
    for (let i = 0; i < N && temp !== null; i++) {
        temp = temp.next;
    }
    current.next = deleteNAfterMRecursive(temp, M, N);
    return head;
}

// Driver code
const nodes = [];
for (let i = 1; i <= 10; i++) {
    nodes.push(new ListNode(i));
}
for (let i = 0; i < 9; i++) {
    nodes[i].next = nodes[i + 1];
}
const M = 2, N = 3;
const newHead = deleteNAfterMRecursive(nodes[0], M, N);
let curr = newHead;
const res = [];
while (curr !== null) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1, 2, 6, 7]

Line Notes

if (head === null) return null;Base case for recursion

for (let i = 1; i < M && current !== null; i++)Skip M nodes carefully

if (current === null) return head;Return if end reached while skipping

for (let i = 0; i < N && temp !== null; i++)Move temp pointer N nodes ahead to delete

current.next = deleteNAfterMRecursive(temp, M, N);Recursive call on remaining list

return head;Return modified list head

⏱

Complexity

TimeO(n)

SpaceO(n/M) due to recursion stack

Each recursive call processes M+N nodes, so total calls ~ n/(M+N). Each call does O(M+N) work, total O(n). Stack depth depends on number of segments.

💡 For large lists, recursion depth can be large and risk stack overflow, but for moderate sizes this is acceptable.

Interview Verdict: Accepted

Elegant and accepted, but recursion depth may be a concern in some environments.

🧠

Optimized Iterative with Early Checks

💡 This approach improves robustness by adding early exit checks and minimizing pointer moves, making it more interview-ready and less error-prone.

Intuition

Use a single pointer to skip M nodes, then delete N nodes by adjusting pointers, with careful null checks to avoid unnecessary iterations.

Algorithm

1. Initialize current pointer at head.
2. While current is not null, skip M-1 nodes with null checks.
3. If current is null after skipping, break early.
4. Delete next N nodes by moving a temporary pointer forward with null checks.
5. Link current node to node after deleted nodes.
6. Move current pointer to continue the process.

💡 This approach is a refined version of brute force that handles edge cases gracefully and avoids redundant operations.

</>

Code

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

def delete_n_after_m_optimized(head, M, N):
    current = head
    while current:
        # Skip M-1 nodes
        for _ in range(1, M):
            if current is None:
                return head
            current = current.next
        if current is None:
            break
        # Delete N nodes
        temp = current.next
        for _ in range(N):
            if temp is None:
                break
            temp = temp.next
        current.next = temp
        current = temp
    return head

# Driver code
if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1, 11)]
    for i in range(9):
        nodes[i].next = nodes[i+1]
    head = nodes[0]
    M, N = 2, 3
    new_head = delete_n_after_m_optimized(head, M, N)
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1, 2, 6, 7]

Line Notes

while current:Loop until end of list

for _ in range(1, M):Skip M-1 nodes with null checks

if current is None:Break early if end reached while skipping

for _ in range(N):Delete N nodes with null checks

current.next = tempLink current node to node after deleted nodes

current = tempMove current pointer forward

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

public class Solution {
    public static ListNode deleteNAfterMOptimized(ListNode head, int M, int N) {
        ListNode current = head;
        while (current != null) {
            for (int i = 1; i < M && current != null; i++) {
                current = current.next;
            }
            if (current == null) break;
            ListNode temp = current.next;
            for (int i = 0; i < N && temp != null; i++) {
                temp = temp.next;
            }
            current.next = temp;
            current = temp;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode curr = head;
        for (int i = 2; i <= 10; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        int M = 2, N = 3;
        ListNode newHead = deleteNAfterMOptimized(head, M, N);
        curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        // Expected output: 1 2 6 7
    }
}

Line Notes

while (current != null)Loop until end of list

for (int i = 1; i < M && current != null; i++)Skip M-1 nodes with null checks

if (current == null) break;Break early if end reached while skipping

for (int i = 0; i < N && temp != null; i++)Delete N nodes with null checks

current.next = temp;Link current node to node after deleted nodes

current = temp;Move current pointer forward

#include <iostream>
using namespace std;

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

ListNode* deleteNAfterMOptimized(ListNode* head, int M, int N) {
    ListNode* current = head;
    while (current) {
        for (int i = 1; i < M && current != nullptr; i++) {
            current = current->next;
        }
        if (current == nullptr) break;
        ListNode* temp = current->next;
        for (int i = 0; i < N && temp != nullptr; i++) {
            ListNode* toDelete = temp;
            temp = temp->next;
            delete toDelete;
        }
        current->next = temp;
        current = temp;
    }
    return head;
}

int main() {
    ListNode* head = new ListNode(1);
    ListNode* curr = head;
    for (int i = 2; i <= 10; i++) {
        curr->next = new ListNode(i);
        curr = curr->next;
    }
    int M = 2, N = 3;
    head = deleteNAfterMOptimized(head, M, N);
    curr = head;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    // Expected output: 1 2 6 7
    return 0;
}

Line Notes

while (current)Loop until end of list

for (int i = 1; i < M && current != nullptr; i++)Skip M-1 nodes with null checks

if (current == nullptr) break;Break early if end reached while skipping

delete toDelete;Free memory of deleted nodes

current->next = temp;Link current node to node after deleted nodes

current = temp;Move current pointer forward

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

function deleteNAfterMOptimized(head, M, N) {
    let current = head;
    while (current !== null) {
        for (let i = 1; i < M && current !== null; i++) {
            current = current.next;
        }
        if (current === null) break;
        let temp = current.next;
        for (let i = 0; i < N && temp !== null; i++) {
            temp = temp.next;
        }
        current.next = temp;
        current = temp;
    }
    return head;
}

// Driver code
const nodes = [];
for (let i = 1; i <= 10; i++) {
    nodes.push(new ListNode(i));
}
for (let i = 0; i < 9; i++) {
    nodes[i].next = nodes[i + 1];
}
const M = 2, N = 3;
const newHead = deleteNAfterMOptimized(nodes[0], M, N);
let curr = newHead;
const res = [];
while (curr !== null) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1, 2, 6, 7]

Line Notes

while (current !== null)Loop until end of list

for (let i = 1; i < M && current !== null; i++)Skip M-1 nodes with null checks

if (current === null) break;Break early if end reached while skipping

for (let i = 0; i < N && temp !== null; i++)Delete N nodes with null checks

current.next = temp;Link current node to node after deleted nodes

current = temp;Move current pointer forward

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the list with minimal pointer moves and early exits improves efficiency and safety.

💡 This approach is the most practical for interviews, balancing clarity and performance.

Interview Verdict: Accepted

This is the recommended approach to implement in interviews due to its clarity and robustness.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimized iterative approach is recommended for interviews due to its clarity, efficiency, and safety.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Iterative)	O(n)	O(1)	No	N/A	Good to explain problem mechanics; acceptable to code
2. Recursive	O(n)	O(n/M) due to recursion stack	Yes	N/A	Good to mention for elegance; avoid coding if large input expected
3. Optimized Iterative	O(n)	O(1)	No	N/A	Best approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Discuss recursive and optimized iterative approaches to demonstrate depth.Write clean, bug-free code with proper pointer handling.Test your code with edge cases and explain your test strategy.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulation, handling edge cases, and writing clean, efficient code.

Common Follow-ups

• What if M or N is zero? → Handle edge cases explicitly.
• Can you do this in one pass? → Yes, the iterative approach is one pass.
• How to handle very large lists? → Use iterative to avoid stack overflow.
• What if the list is circular? → Detect and handle cycles before processing.

💡 These follow-ups test your robustness and ability to adapt your solution to variations and constraints.

🔍

Pattern Recognition

When to Use

1) You need to skip and delete nodes in a linked list repeatedly; 2) The problem mentions keeping M nodes and deleting N nodes; 3) You must manipulate pointers carefully; 4) The problem fits a two-pointer or fast-slow pointer pattern.

Signature Phrases

'skip M nodes and delete N nodes''delete N nodes after M nodes'

NOT This Pattern When

Problems that only require traversal or reversal without skipping/deleting nodes are different patterns.

Similar Problems

Remove Nth Node From End of List - similar pointer manipulationLinked List Cycle Detection - uses fast and slow pointersSkip M Delete N Nodes - direct variant of this problem

Practice

1. What is the time complexity of the optimized fast-slow pointer algorithm for detecting a cycle in a circular array of length n, where each element can be positive or negative steps? Assume the algorithm marks visited elements in-place to avoid repeated work.

medium

A. O(n) because each element is visited at most twice due to in-place marking

B. O(n) average but O(n^2) worst-case if cycles overlap heavily

C. O(n log n) due to repeated modulo operations and pointer jumps

D. O(n^2) because each element can be visited multiple times during cycle checks

Solution

1. Step 1: Analyze outer and inner loops

   Each index is processed once in the outer loop; inner while loop visits elements until cycle or zero marking.

2. Step 2: Check effect of in-place marking

   Marking visited elements as zero prevents revisiting, ensuring total visits across all iterations is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place marking guarantees linear time complexity [OK]

Hint: In-place marking -> each element visited once [OK]

Common Mistakes:

• Assuming repeated visits cause O(n²)
• Ignoring marking effect
• Confusing modulo cost as log factor

2. What is the time complexity of Floyd's Tortoise and Hare algorithm for finding the duplicate number in an array of size n+1 with values from 1 to n?

medium

A. O(n) because each pointer moves at most n steps before meeting

B. O(n^2) due to nested pointer updates

C. O(n log n) due to implicit sorting in pointer jumps

D. O(n) but with O(n) extra space for visited nodes

Solution

1. Step 1: Analyze pointer movements

   Slow pointer moves one step at a time, fast pointer moves two steps. They meet within O(n) steps because the cycle length is at most n.

2. Step 2: Confirm no nested loops or extra space

   There are no nested loops; each iteration advances pointers. Space is O(1), so no extra overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time complexity matches pointer traversal count [OK]

Hint: Two pointers meet in linear time, no nested loops [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing pointer jumps with sorting complexity
• Thinking extra space is used for visited nodes

3. What is the space complexity of the recursive reorderList implementation shown below, considering a linked list of length n?

medium

A. O(log n) -- recursion divides list in halves

B. O(1) -- only constant extra pointers used

C. O(n) -- recursion stack grows linearly with list length

D. O(n^2) -- nested recursive calls cause quadratic space

Solution

1. Step 1: Analyze recursion depth

   Each recursive call moves one node forward, so recursion depth is n.

2. Step 2: Determine space usage

   Each call adds a stack frame, so total auxiliary space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack grows linearly with input size [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming recursion is O(1) space
• Confusing recursion with divide-and-conquer
• Thinking nested calls multiply space

4. Suppose the linked list nodes can be reused multiple times in cycles (i.e., cycles can overlap or nest). Which modification to the fast-slow pointer approach correctly detects and counts the length of the first cycle encountered?

hard

A. Use a hash set to track visited nodes to detect cycles and count length, since fast-slow pointers fail with overlapping cycles.

B. Modify the fast pointer to move three steps at a time to detect overlapping cycles faster.

C. Run the fast-slow pointer detection multiple times from different starting points to find all cycles.

D. Use fast-slow pointers as usual; overlapping cycles do not affect detection of the first cycle.

Solution

1. Step 1: Understand overlapping cycles scenario

   Overlapping or nested cycles mean fast-slow pointers may not reliably detect all cycles or count lengths correctly.

2. Step 2: Evaluate approaches for correctness

   Using a hash set tracks all visited nodes, ensuring detection of any cycle and accurate length counting despite overlaps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set approach handles complex cycle structures correctly [OK]

Hint: Fast-slow pointers detect only simple cycles reliably [OK]

Common Mistakes:

• Assuming fast-slow pointers handle overlapping cycles
• Increasing fast pointer speed breaks correctness
• Multiple runs of fast-slow pointers are inefficient and incomplete

5. Suppose the problem is modified so that the linked list may contain cycles or repeated nodes, and you must reorder the list without using extra space or modifying node values. Which approach correctly handles this variant without causing infinite loops?

hard

A. First detect and remove cycles using Floyd's cycle detection, then apply the standard reorder algorithm.

B. Use the brute force approach with an array to reorder nodes, ignoring cycles since array stores nodes once.

C. Store visited nodes in a hash set during reorder to avoid revisiting nodes, then reorder using brute force.

D. Use the recursive reorderList as is, trusting the stop condition to prevent cycles.

Solution

1. Step 1: Understand problem variant

   Input may have cycles or repeated nodes, so naive reorder risks infinite loops.

2. Step 2: Choose safe approach

   Detect and remove cycles first (e.g., Floyd's algorithm), then reorder safely in-place.

3. Step 3: Evaluate other options

   Recursive reorder assumes no cycles; hash set uses extra space; brute force ignores cycles causing issues.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Cycle removal is prerequisite for safe reorder [OK]

Hint: Remove cycles before reorder to avoid infinite loops [OK]

Common Mistakes:

• Assuming reorder works on cyclic lists
• Ignoring cycle detection
• Using extra space when disallowed