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 need to determine if it reads the same forwards and backwards. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use fast and slow pointers to find the middle, reverse the second half in-place, then compare both halves.

B. Convert the linked list to an array and check palindrome by comparing elements from both ends.

C. Use a hash set to store visited nodes and check for palindrome by comparing values.

D. Use a recursive approach to compare nodes from start and end simultaneously.

Solution

1. Step 1: Identify the problem constraints

   The problem requires checking palindrome in O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Converting to array uses O(n) space, recursion uses O(n) stack space, and hash set is not suitable for palindrome check. Using fast and slow pointers to reverse second half in-place meets both time and space requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses fast-slow pointers and in-place reversal [OK]

Hint: Optimal palindrome check uses fast-slow pointers and in-place reversal [OK]

Common Mistakes:

• Assuming array conversion is optimal due to simplicity
• Believing recursion uses constant space
• Using hash sets for palindrome detection

2. What is the time complexity of the optimized fast and slow pointer approach for detecting a circular array loop in an array of length n?

medium

A. O(n^2) because each element may be visited multiple times

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

C. O(n) because each element is visited at most once due to marking visited elements

D. O(n) amortized but worst case can be O(n^2) if cycles overlap

Solution

1. Step 1: Identify outer loop and inner pointer movements

   The outer loop runs n times, but elements are marked zero once visited, preventing reprocessing.

2. Step 2: Analyze pointer visits

   Each element is visited at most once in the inner while loop due to zero marking, so total work is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Marking visited elements ensures linear time complexity [OK]

Hint: Marking visited elements prevents repeated work -> O(n) [OK]

Common Mistakes:

• Assuming repeated visits cause O(n^2)
• Confusing modulo cost as log factor
• Believing overlapping cycles increase complexity

3. Identify the bug in the following Python code for checking if a number is happy. The code attempts to detect cycles using recursion but lacks proper cycle detection.

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    def helper(num):
        if num == 1:
            return true
        return helper(get_next(num))

    return helper(n)

medium

A. Missing base case for cycle detection causing infinite recursion

B. Incorrect sum of squares calculation in get_next function

C. Returning helper(get_next(num)) without checking if num is 1

D. Not initializing total_sum to zero before summing digits

Solution

1. Step 1: Analyze recursion base cases

   The code only stops recursion if num == 1. It does not detect cycles, so for unhappy numbers it recurses infinitely.

2. Step 2: Identify missing cycle detection

   Without tracking visited numbers or using fast-slow pointers, the recursion never terminates for cycles, causing stack overflow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite recursion due to missing cycle detection base case [OK]

Hint: Check for cycle detection in recursion to avoid infinite loops [OK]

Common Mistakes:

• Assuming recursion stops at cycles without explicit detection

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