Remove Nth Node From End of List

📋

Problem

Imagine managing a playlist where you want to remove the song that is Nth from the end without counting the entire list every time.

Given the head of a singly linked list and an integer n, remove the nth node from the end of the list and return its head.

The number of nodes in the list is at least 1 and at most 10^51 ≤ n ≤ number of nodes in the list

Edge cases: List has only one node and n=1 → result is an empty listn equals the length of the list → remove the head noden is 1 → remove the last node

</>

IDE

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:public ListNode removeNthFromEnd(ListNode head, int n)ListNode* removeNthFromEnd(ListNode* head, int n)function removeNthFromEnd(head, n)

def removeNthFromEnd(head, n):
    # Write your solution here
    pass

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // Write your solution here
    return nullptr;
}

function removeNthFromEnd(head, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2, 3, 4, 5]Did not remove any node; forgot to update pointers after identifying node to remove.✅ After locating node before target, set slow.next = slow.next.next to remove target node.

Wrong: [2, 3, 4, 5]Incorrectly removed head node when n is not equal to list length.✅ Use dummy node and move fast pointer n steps ahead before moving slow pointer.

Wrong: [1, 2, 3, 4]Removed last node incorrectly when n=1 due to greedy removal by value.✅ Use two-pointer technique to remove node by position, not by value.

Wrong: [1, 2, 4, 5]Off-by-one error causing removal of wrong node when n=3.✅ Move fast pointer n steps ahead, not n-1, before moving slow pointer.

Wrong: Timeout or no outputUsing recursive or multiple pass approach causing TLE on large inputs.✅ Implement one-pass two-pointer approach to achieve O(n) time complexity.

✓

Test Cases

Try testing your code with smallest and boundary inputs to catch base case bugs.

Consider tricky indexing and position-based removal to avoid common logical errors.

Focus on algorithmic complexity; use two-pointer technique to achieve linear time.

t1_01basic

Input{"head":[1,2,3,4,5],"n":2}

Expected[1,2,3,5]

⏱ Performance - must finish in 2000ms

The 2nd node from the end is '4'. Removing it results in the list [1,2,3,5].

💡 Use two pointers with a fixed gap of n nodes between them.

💡 Advance the fast pointer n steps first, then move both pointers until fast reaches the end.

💡 Use a dummy head to handle edge cases like removing the first node.

Why it failed: Failed to remove the correct node from the end. Possibly did not maintain the n-node gap or forgot dummy head. Fix by initializing dummy node and moving fast pointer n steps ahead before moving slow.

✓ Correctly removed the nth node from the end using two-pointer technique.

t1_02basic

Input{"head":[10,20,30,40,50,60],"n":4}

Expected[10,20,40,50,60]

⏱ Performance - must finish in 2000ms

The 4th node from the end is '30'. Removing it results in [10,20,40,50,60].

💡 Remember to use a dummy node to simplify removal of head or middle nodes.

💡 Keep the gap of n between fast and slow pointers before moving both.

💡 After fast reaches the end, slow.next is the node to remove.

Why it failed: Incorrect node removed or list structure corrupted. Likely lost track of slow pointer or did not use dummy head. Fix by ensuring slow pointer stops at node before target and dummy head is used.

✓ Successfully removed the correct node maintaining list integrity.

t2_01edge

Input{"head":[1],"n":1}

Expected[]

⏱ Performance - must finish in 2000ms

Single node list with n=1 means removing the only node, resulting in an empty list.

💡 Consider the case where the list has only one node.

💡 Use a dummy node to handle removal of the head node cleanly.

💡 Return dummy.next which may be None if list becomes empty.

Why it failed: Failed to handle single node removal resulting in empty list. Possibly did not handle dummy.next correctly. Fix by always returning dummy.next after removal.

✓ Correctly handled single node removal resulting in empty list.

t2_02edge

Input{"head":[5,6,7,8],"n":4}

Expected[6,7,8]

⏱ Performance - must finish in 2000ms

n equals the length of the list, so the head node '5' is removed.

💡 When n equals list length, the node to remove is the head.

💡 Use a dummy node to simplify removing the head node.

💡 After moving fast pointer n steps, slow will be at dummy node before head.

Why it failed: Did not remove head node when n equals list length. Likely forgot dummy node or incorrect pointer movement. Fix by using dummy node and moving fast pointer n steps before slow.

✓ Correctly removed head node when n equals list length.

t2_03edge

Input{"head":[9,9,9,9,9],"n":1}

Expected[9,9,9,9]

⏱ Performance - must finish in 2000ms

Removing the last node (n=1) from a list with all identical values.

💡 Ensure you remove the correct node even if values are identical.

💡 Use pointer positions, not values, to identify the node to remove.

💡 After fast pointer reaches end, slow.next is the node to remove.

Why it failed: Removed wrong node due to relying on node values instead of positions. Fix by using two-pointer technique to identify node by position, not value.

✓ Correctly removed last node by position, not value.

t3_01corner

Input{"head":[1,2,3,4,5],"n":5}

Expected[2,3,4,5]

⏱ Performance - must finish in 2000ms

Removing the head node by specifying n equal to list length, testing off-by-one errors.

💡 Check if your pointers correctly handle the case when n equals list length.

💡 Ensure dummy node is used to avoid null pointer exceptions.

💡 Move fast pointer exactly n steps before moving slow pointer.

Why it failed: Off-by-one error causing wrong node removal or crash. Fix by moving fast pointer n steps ahead, not n-1.

✓ Handled off-by-one correctly, removed head node as expected.

t3_02corner

Input{"head":[1,2,3,4,5],"n":1}

Expected[1,2,3,4]

⏱ Performance - must finish in 2000ms

Removing the last node to catch greedy approach mistakes that remove first matching value instead of nth from end.

💡 Do not remove node by value; use position from end.

💡 Use two-pointer technique to find exact node to remove.

💡 After fast pointer reaches end, slow.next is the node to remove.

Why it failed: Greedy approach removing first matching value instead of nth from end. Fix by using two-pointer method to identify node by position.

✓ Correctly removed last node by position, not by value.

t3_03corner

Input{"head":[1,2,3,4,5],"n":3}

Expected[1,2,4,5]

⏱ Performance - must finish in 2000ms

Testing confusion between 0/1-based indexing; the 3rd node from end is '3'.

💡 Remember that n is 1-based from the end, not 0-based.

💡 Advance fast pointer n steps ahead before moving slow.

💡 Slow pointer will stop at node before the one to remove.

Why it failed: Indexing confusion causing removal of wrong node. Fix by moving fast pointer n steps ahead, not n-1.

✓ Correctly handled 1-based indexing to remove nth node from end.

t4_01performance

Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"n":50}

Expectednull

⏱ Performance - must finish in 2000ms

List of length 100, removing 50th node from end. Algorithm must run in O(n) time within 2 seconds.

💡 Use two-pointer technique to achieve O(n) time complexity.

💡 Avoid multiple passes or recursion to prevent TLE.

💡 Use a dummy node and move fast pointer n steps ahead before slow.

Why it failed: TLE due to using O(n^2) or recursive approach without optimization. Fix by implementing one-pass two-pointer method.

✓ Algorithm runs in O(n) time and passes performance constraints.

Practice

1. You are given a singly linked list and two integers M and N. The task is to traverse the list, skip M nodes, then delete the next N nodes, and repeat this process until the end of the list. Which algorithmic approach best guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Use a recursive approach that deletes nodes during the unwinding phase of recursion.

B. Use a brute force nested loop approach that for each node checks ahead to delete N nodes repeatedly.

C. Use an iterative two-pointer approach that skips M nodes and deletes N nodes in a single pass.

D. Use a dynamic programming approach to store states of nodes to decide deletion.

Solution

1. Step 1: Understand the problem constraints

   The problem requires skipping M nodes and deleting N nodes repeatedly until the list ends, which suggests a linear traversal.

2. Step 2: Evaluate approaches

   Recursive approaches add extra space due to call stack; brute force nested loops increase time complexity; dynamic programming is unnecessary as no overlapping subproblems exist. The iterative two-pointer approach efficiently traverses once, skipping and deleting nodes in O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative two-pointer approach matches optimal time and space complexity [OK]

Hint: Iterative two-pointer approach is linear and space efficient [OK]

Common Mistakes:

• Thinking recursion is optimal despite extra stack space
• Using nested loops causing O(n²) time
• Misapplying DP to a linear traversal problem

2. Consider the following code snippet for detecting and returning the length of a cycle in a linked list. Given the linked list: 3 -> 2 -> 0 -> -4 -> (back to node with value 2), what is the returned cycle length?

easy

A. 2

B. 3

C. 4

D. 0

Solution

1. Step 1: Trace fast and slow pointers until they meet

   Slow moves 1 step, fast moves 2 steps. They meet at node with value 2 after some iterations.

2. Step 2: Count cycle length by moving slow pointer until it meets fast again

   Starting from node 2, slow moves through nodes 0, -4, then back to 2, counting 3 nodes total.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Cycle length is nodes 2 -> 0 -> -4 -> back to 2 = 3 [OK]

Hint: Cycle length equals number of unique nodes in loop [OK]

Common Mistakes:

• Off-by-one counting cycle length
• Confusing meeting point with cycle start
• Returning 0 when cycle exists

3. 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

4. Consider the following buggy code for finding the middle node of a linked list. Which line contains the subtle bug that can cause a runtime error?

medium

A. Line 4: while fast.next and fast.next.next:

B. Line 3: fast = head

C. Line 2: slow = head

D. Line 6: return slow

Solution

1. Step 1: Analyze loop condition

   The condition checks fast.next and fast.next.next but does not check if fast itself is null, which can cause AttributeError if fast is null.

2. Step 2: Identify fix

   Change condition to while fast and fast.next to safely access fast.next.next.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing fast null check causes runtime error on short lists [OK]

Hint: Always check fast pointer is not null before accessing next [OK]

Common Mistakes:

• Assuming fast.next is safe without checking fast
• Returning first middle node incorrectly
• Modifying list nodes accidentally

5. Consider the following buggy code snippet for splitting a linked list into k parts. Which line contains the subtle bug that can cause parts to remain connected, leading to incorrect output or infinite loops?

medium

A. Line where current.next is set to null (missing in this code)

B. Line where parts[i] is assigned

C. Line where remainder is decremented

D. Line where total_nodes is counted

Solution

1. Step 1: Identify missing link break

   The code comments out the lines that break the link after each part, so parts remain connected.

2. Step 2: Understand impact

   Without setting current.next = null, parts share nodes, causing incorrect output or infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Breaking links is essential to separate parts [OK]

Hint: Always break links to separate parts [OK]

Common Mistakes:

• Forgetting to break links
• Misplacing remainder decrement
• Incorrectly assigning parts[i]