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. You are given a circular array where each element represents a jump length and direction (positive for forward, negative for backward). The task is to determine if there exists a cycle in the array such that the cycle is longer than one element and all jumps are in the same direction. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to jump as far as possible from each index until a cycle is detected or no progress is made.

B. Dynamic programming to store reachable indices and detect cycles by memoization.

C. Brute force simulation from each index checking all possible cycles exhaustively.

D. Fast and slow pointer cycle detection that checks direction consistency and avoids single-element loops.

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify suitable algorithm

   Fast and slow pointer cycle detection efficiently finds cycles in O(n) time while checking direction and cycle length constraints.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast and slow pointers detect cycles without exhaustive search [OK]

Hint: Cycle detection with direction check -> fast-slow pointers [OK]

Common Mistakes:

• Assuming greedy jumps always find cycles
• Using DP which is inefficient here
• Brute force is correct but not optimal

2. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

3. You are given a singly linked list and an integer n. The task is to remove the n-th node from the end of the list in a single pass without using extra space for storing nodes. Which approach guarantees this optimal solution?

easy

A. Traverse the list twice: first to count nodes, second to remove the target node.

B. Sort the list first, then remove the node at position length - n.

C. Use two pointers with a fixed gap of n+1 nodes, moving together until the fast pointer reaches the end.

D. Use a dynamic programming approach to store intermediate results for each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing the n-th node from the end in one pass without extra storage.

2. Step 2: Identify the two-pointer technique for single-pass removal

   Using two pointers with a gap of n+1 nodes ensures the slow pointer stops just before the target node, allowing removal in one pass.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n+1 enable single-pass removal [OK]

Common Mistakes:

• Using two passes instead of one
• Trying to sort the list which is unnecessary
• Confusing DP with linked list traversal

4. What is the space complexity of the optimal palindrome linked list check that reverses the second half in-place?

medium

A. O(n) due to storing node values in an array

B. O(1) because reversal is done in-place without extra data structures

C. O(log n) due to recursion stack in reversal

D. O(n) due to recursion stack in reversal

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm reverses the second half in-place using pointers, no extra arrays or stacks.

2. Step 2: Check for recursion stack

   The reversal is iterative, so no recursion stack space is used.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative reversal uses constant extra space [OK]

Hint: Iterative reversal uses O(1) space, recursion would add stack space [OK]

Common Mistakes:

• Confusing iterative reversal with recursive reversal
• Assuming array storage is needed for palindrome check
• Forgetting recursion stack space in complexity

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