Remove Nth Node from End of List in DSA C++ - Time & Space Complexity

Time Complexity: Remove Nth Node from End of List

O(n)

Understanding Time Complexity

We want to understand how the time needed to remove the nth node from the end of a linked list changes as the list grows.

How does the number of steps grow when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* fast = dummy;
    ListNode* slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return dummy->next;
}
    

This code removes the nth node from the end by using two pointers moving through the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two pointer traversals through the linked list.
• How many times: The first loop moves the fast pointer n steps; the second loop moves both pointers until fast reaches the end, roughly (length - n) steps.

How Execution Grows With Input

As the list size grows, the number of steps grows roughly in a straight line with the list length.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The steps increase directly with the list size, so doubling the list roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to remove the nth node from the end grows linearly with the size of the list.

Common Mistake

[X] Wrong: "Since we only move the fast pointer n steps first, the time is O(n) where n is the position from the end, not the list length."

[OK] Correct: Because after moving fast n steps, we still move both pointers through the rest of the list, which depends on the total list length, not just n.

Interview Connect

Understanding this linear time approach shows you can efficiently handle linked list problems using two pointers, a common and useful skill in coding challenges.

Self-Check

"What if we used a single pass with extra memory to store nodes? How would the time complexity change?"

Practice

1. What does the problem "Remove Nth Node from End of List" ask you to do with a linked list?

easy

A. Add a new node at the Nth position from the end

B. Remove the node that is Nth from the start of the list

C. Reverse the linked list

D. Remove the node that is Nth from the end of the list

Solution

1. Step 1: Understand the problem statement

   The problem asks to remove the node that is Nth from the end of the linked list, not from the start or to reverse or add nodes.

2. Step 2: Clarify the operation on the list

   Removing the Nth node from the end means counting nodes from the tail backwards and deleting that node.

3. Final Answer:

   Remove the node that is Nth from the end of the list -> Option D

4. Quick Check:

   Remove Nth from end = Remove Nth from end [OK]

Hint: Focus on counting nodes from the list's end, not start [OK]

Common Mistakes:

• Confusing Nth from end with Nth from start
• Thinking the problem asks to reverse the list
• Trying to add nodes instead of removing

2. Which of the following C++ function signatures correctly represents a function to remove the Nth node from the end of a singly linked list?

easy

A. ListNode* removeNthFromEnd(ListNode* head, int n);

B. void removeNthFromEnd(int n, ListNode* head);

C. ListNode removeNthFromEnd(ListNode head, int n);

D. ListNode* removeNthFromEnd(int n);

Solution

1. Step 1: Check parameter order and types

   The function should take the head pointer of the list and the integer n as parameters, with head first and n second.

2. Step 2: Check return type

   Since the head might change (if first node is removed), the function returns a pointer to the new head.

3. Final Answer:

   ListNode* removeNthFromEnd(ListNode* head, int n); -> Option A

4. Quick Check:

   Correct signature = ListNode* removeNthFromEnd(ListNode* head, int n); [OK]

Hint: Function returns new head pointer and takes head, n as parameters [OK]

Common Mistakes:

• Wrong parameter order
• Returning ListNode instead of pointer
• Missing head parameter

3. What will be the output linked list after removing the 2nd node from the end in the list 1 -> 2 -> 3 -> 4 -> 5 -> null?

medium

A. 1 -> 2 -> 3 -> 5 -> null

B. 2 -> 3 -> 4 -> 5 -> null

C. 1 -> 3 -> 4 -> 5 -> null

D. 1 -> 2 -> 4 -> 5 -> null

Solution

1. Step 1: Identify the 2nd node from the end

   Counting from the end: 5 (1st), 4 (2nd). So node with value 4 is to be removed.

2. Step 2: Remove node 4 and link previous node to next

   Node 3's next pointer now points to node 5, skipping node 4.

3. Final Answer:

   1 -> 2 -> 3 -> 5 -> null -> Option A

4. Quick Check:

   Remove 2nd from end = Remove node 4 [OK]

Hint: Count nodes from end to find which to remove [OK]

Common Mistakes:

• Removing wrong node counting from start
• Not updating links correctly
• Confusing 2nd from end with 2nd from start

4. Given the following code snippet to remove the Nth node from the end, what is the bug?

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* fast = head;
    ListNode* slow = head;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    while (fast->next != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return head;
}

medium

A. Uses wrong loop condition in for loop

B. Does not handle case when n equals list length (removing head)

C. Returns wrong pointer type

D. Does not move slow pointer at all

Solution

1. Step 1: Analyze fast pointer movement

   Fast pointer moves n steps ahead. If n equals list length, fast becomes nullptr.

2. Step 2: Check while loop condition

   While loop uses fast->next, but if fast is nullptr, accessing fast->next causes error. Also, removing head node is not handled.

3. Final Answer:

   Does not handle case when n equals list length (removing head) -> Option B

4. Quick Check:

   Edge case for head removal missing [OK]

Hint: Check edge cases when fast pointer reaches null early [OK]

Common Mistakes:

• Ignoring removal of head node
• Accessing fast->next without null check
• Not updating head pointer when needed

5. You want to remove the 3rd node from the end of a linked list with nodes: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null. Which of the following steps correctly describes the process using two pointers?

hard

A. Move slow pointer 3 steps ahead, then move fast pointer until slow reaches end, then remove fast's next node.

B. Move fast pointer 3 steps ahead, then move slow pointer 3 steps ahead, then remove head node.

C. Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node.

D. Move both pointers together from start without offset, then remove the node at position 3.

Solution

1. Step 1: Initialize two pointers at head

   Start both fast and slow pointers at the head of the list.

2. Step 2: Move fast pointer n steps ahead

   Move fast pointer 3 steps ahead to create a gap of 3 nodes between fast and slow.

3. Step 3: Move both pointers until fast reaches end

   Move fast and slow pointers one step at a time until fast reaches the last node.

4. Step 4: Remove the node after slow pointer

   Slow pointer now points to node before the target; remove slow->next node.

5. Final Answer:

   Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node. -> Option C

6. Quick Check:

   Two-pointer gap method = Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node. [OK]

Hint: Use two pointers with gap n to find node before target [OK]

Common Mistakes:

• Moving slow pointer first instead of fast
• Removing wrong node after pointers move
• Not creating correct gap between pointers