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 two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. You need to add the two numbers and return the sum as a linked list. Which approach guarantees an optimal solution with O(max(m, n)) time and O(1) extra space?

easy

A. Use a recursive approach that creates a new list for the sum, handling carry via recursion.

B. Iteratively traverse both lists simultaneously, modifying one list in-place to store the sum and carry.

C. Convert both linked lists to integers, add them, then convert the sum back to a linked list.

D. Use a brute force approach that creates a new list node for each digit sum, ignoring in-place modification.

Solution

1. Step 1: Understand the problem constraints

   The problem requires adding two numbers represented as linked lists in reverse order, aiming for optimal time and space.

2. Step 2: Identify the approach that modifies input in-place

   Iterative traversal with in-place modification reuses existing nodes, achieving O(max(m, n)) time and O(1) extra space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative approach avoids extra space and handles carry efficiently [OK]

Hint: In-place iterative approach saves space and time [OK]

Common Mistakes:

• Assuming recursion is always optimal
• Ignoring space complexity by creating new nodes
• Converting lists to integers causes overflow

2. Consider the following code snippet implementing the two-pointer approach to find the intersection of two linked lists. Given the lists: listA: 1 -> 2 -> 3 -> 4 -> 5 listB: 9 -> 4 -> 5 where nodes with values 4 and 5 are shared (intersection starts at node with value 4). What is the value returned by the function?

easy

A. 3

B. 4

C. 5

D. No intersection

Solution

1. Step 1: Trace pointers through lists

   pA starts at 1, pB at 9. They advance until pA reaches 4, pB reaches 4 (intersection node). Since nodes are shared, pA is pB at node with value 4.

2. Step 2: Confirm return value

   The function returns the intersection node, which has value 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Intersection node value is 4 as expected [OK]

Hint: Pointers meet at shared node 4 [OK]

Common Mistakes:

• Returning node value instead of node reference
• Confusing next pointers
• Off-by-one in pointer switching

3. You are given a singly linked list with unsorted integer values. You need to sort the list in ascending order with O(n log n) time complexity and O(1) auxiliary space. Which algorithmic approach best fits this requirement?

easy

A. Perform a bottom-up iterative merge sort directly on the linked list without extra arrays.

B. Use a recursive quicksort on the linked list by partitioning around a pivot node.

C. Extract all values into an array, sort the array using quicksort, then rebuild the linked list.

D. Apply a greedy insertion sort by inserting nodes into a new sorted list one by one.

Solution

1. Step 1: Understand time and space constraints

   The problem requires O(n log n) time and O(1) auxiliary space, which rules out array extraction and recursive approaches that use extra space.

2. Step 2: Identify algorithm matching constraints

   Bottom-up iterative merge sort on linked lists achieves O(n log n) time and O(1) space by merging sublists iteratively without recursion or extra arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bottom-up merge sort is the standard in-place linked list sorting method [OK]

Hint: Bottom-up merge sort is in-place and O(n log n) [OK]

Common Mistakes:

• Thinking quicksort is efficient on linked lists due to lack of random access
• Assuming insertion sort is efficient for large lists
• Believing array extraction is O(1) space

4. You are given a singly linked list and asked to swap every two adjacent nodes, returning the modified list. Which approach guarantees an optimal solution that swaps nodes in-place without extra data structures and handles all edge cases efficiently?

easy

A. Use a greedy approach that swaps values instead of nodes to minimize pointer changes.

B. Use a recursive approach that swaps pairs by adjusting pointers and recurses on the rest of the list.

C. Use dynamic programming to store intermediate swapped sublists for reuse.

D. Use a brute force approach that creates a new list and inserts nodes in swapped order.

Solution

1. Step 1: Understand the problem constraints

   The problem requires swapping nodes in pairs by changing pointers, not just values, and must be done in-place.

2. Step 2: Identify the approach that swaps nodes recursively

   The recursive approach swaps the first two nodes, then recursively swaps the rest, ensuring all pairs are swapped correctly without extra space for new lists.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive pointer swapping matches problem requirements [OK]

Hint: Recursive pointer swapping fits in-place pairwise node swaps [OK]

Common Mistakes:

• Thinking swapping values is sufficient
• Using DP unnecessarily
• Creating new lists wastes space

5. What is the space complexity of the tail-recursive reversal approach for reversing a singly linked list of length n, and why might a common misconception about it be incorrect?

medium

A. O(1) because the reversal is done in-place with constant extra pointers.

B. O(n) because the recursion stack grows linearly with the list length.

C. O(n) because an auxiliary array is used to store nodes during reversal.

D. O(log n) because tail recursion optimizes the stack usage to logarithmic depth.

Solution

1. Step 1: Identify recursion stack usage

   Each recursive call adds a frame to the call stack until the base case is reached, so for n nodes, stack depth is n.

2. Step 2: Analyze auxiliary space

   No extra arrays or data structures are used, so auxiliary space besides recursion stack is O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursion stack causes O(n) space, not constant [OK]

Hint: Recursion stack adds O(n) space despite in-place pointer changes [OK]

Common Mistakes:

• Assuming tail recursion is optimized to O(1) stack in Python
• Confusing auxiliary data structures with recursion stack