Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Remove Nth Node From End of List

MEDIUMProblemSolveExternal Links

Description

You are given the head of a singly linked list. Your task is to remove the node that is positioned at the nth place from the end of the list, and then return the head of the modified list.

In a singly linked list, each node contains a value and a pointer to the next node. The last node points to null. When we say "nth node from the end," we mean counting backwards from the last node. For example, in a list with 5 nodes, the 1st node from the end is the last node, and the 2nd node from the end is the second-to-last node.

After removing the target node, the remaining nodes should stay connected in their original order.

Examples

Example 1

Input: head = [1, 2, 3, 4, 5], n = 2

Output: [1, 2, 3, 5]

Explanation: The list has 5 nodes. Counting from the end, the 2nd node is the one with value 4. Removing it leaves us with [1, 2, 3, 5]. Node 3 now points directly to node 5, bypassing the removed node 4.

Example 2

Input: head = [1], n = 1

Output: []

Explanation: The list has only one node, and we need to remove the 1st node from the end (which is the only node). After removal, the list is empty.

Example 3

Input: head = [1, 2], n = 1

Output: [1]

Explanation: The list has 2 nodes. The 1st node from the end is the last node (value 2). Removing it leaves us with just [1].

Constraints

  • The number of nodes in the list is sz
  • 1 ≤ sz ≤ 30
  • 0 ≤ Node.val ≤ 100
  • 1 ≤ n ≤ sz

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to convert the "nth from the end" into a position from the beginning. If we know the total length of the list is L, then the nth node from the end is the (L - n + 1)th node from the beginning. But to find L, we need to traverse the entire list first.

Think of it like a line of people standing in a row. If someone tells you "remove the 2nd person from the back," you would first count how many people are in the line, then walk to the right position from the front to remove that person.

So the brute force approach uses two passes:

  1. First pass: Walk through the entire list to count the total number of nodes.
  2. Second pass: Walk (L - n) steps from the beginning to reach the node just before the target, then skip over the target node.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5], n = 2:

Pass 1: Count the total length

Step 1: Start at head (node 1). Count = 1.

Step 2: Move to node 2. Count = 2.

Step 3: Move to node 3. Count = 3.

Step 4: Move to node 4. Count = 4.

Step 5: Move to node 5. Count = 5. Next is null, so we stop. Total length L = 5.

Pass 2: Navigate to the target's predecessor

Step 6: We need to remove the (L - n + 1) = (5 - 2 + 1) = 4th node from the beginning (value 4). We need to reach the 3rd node (its predecessor). Using a dummy node before head, we walk (L - n) = 3 steps.

Step 7: Start at dummy → after 1 step, at node 1 → after 2 steps, at node 2 → after 3 steps, at node 3.

Step 8: Node 3 is the predecessor. Set node 3's next to node 5 (skipping node 4).

Step 9: Return dummy.next which is node 1. Result: [1, 2, 3, 5].

Two-Pass Approach — Count Then Remove — First we traverse the entire list to count nodes, then we walk to the predecessor of the target node and remove it by updating the link.

Algorithm

  1. Create a dummy node that points to the head (to handle the edge case where the head itself needs to be removed)
  2. Traverse the entire list to count the total number of nodes (L)
  3. Calculate the position from the beginning: the target is the (L - n + 1)th node, so we need to reach its predecessor at position (L - n)
  4. Starting from the dummy node, walk (L - n) steps to reach the predecessor
  5. Set predecessor.next = predecessor.next.next to bypass the target node
  6. Return dummy.next as the new head

Code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // First pass: count total nodes
        int length = 0;
        ListNode* curr = head;
        while (curr != nullptr) {
            length++;
            curr = curr->next;
        }
        
        // Create dummy node to handle edge case of removing head
        ListNode* dummy = new ListNode(0, head);
        
        // Second pass: walk (length - n) steps from dummy
        curr = dummy;
        for (int i = 0; i < length - n; i++) {
            curr = curr->next;
        }
        
        // Remove the target node
        ListNode* toDelete = curr->next;
        curr->next = curr->next->next;
        delete toDelete;
        
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # First pass: count total nodes
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next
        
        # Create dummy node to handle edge case of removing head
        dummy = ListNode(0, head)
        
        # Second pass: walk (length - n) steps from dummy
        curr = dummy
        for _ in range(length - n):
            curr = curr.next
        
        # Remove the target node
        curr.next = curr.next.next
        
        return dummy.next
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // First pass: count total nodes
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        
        // Create dummy node to handle edge case of removing head
        ListNode dummy = new ListNode(0, head);
        
        // Second pass: walk (length - n) steps from dummy
        curr = dummy;
        for (int i = 0; i < length - n; i++) {
            curr = curr.next;
        }
        
        // Remove the target node
        curr.next = curr.next.next;
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(L)

We traverse the linked list twice. The first pass counts all L nodes, and the second pass walks at most L nodes to reach the predecessor. Total: 2L operations, which simplifies to O(L).

Space Complexity: O(1)

We only use a constant amount of extra space: the dummy node, a counter variable, and a pointer. No additional data structures that scale with input size are needed.

Why This Approach Is Not Efficient

The two-pass approach works correctly with O(L) time and O(1) space, which is already quite efficient. However, it requires traversing the list twice — once to count and once to remove. For very long lists, this means we visit every node at least once and some nodes twice.

The key question is: can we find and remove the nth node from the end in a single pass? If we could maintain a fixed gap between two pointers, the trailing pointer would naturally land at the right position when the leading pointer reaches the end. This is the two-pointer (fast and slow) technique, which avoids the need to count the total length at all.

While both approaches are O(L) in time complexity, the one-pass solution is more elegant and performs fewer total operations in practice. It also demonstrates a powerful technique that applies to many linked list problems.

Optimal Approach - Two Pointers (One Pass)

Intuition

Imagine two runners on a track that has a finish line at the end. If one runner starts n steps ahead of the other, and both run at the same speed, when the front runner crosses the finish line, the back runner will be exactly n steps behind the finish line.

We apply this same idea to the linked list. We use two pointers: a fast pointer and a slow pointer. Both start at a dummy node placed before the head. First, we advance the fast pointer n steps ahead. Now there is a gap of exactly n nodes between the two pointers. Then we move both pointers forward simultaneously, one step at a time. When the fast pointer reaches the very last node (its next is null), the slow pointer will be positioned right before the node we want to remove.

The dummy node is a critical trick here. Without it, if we need to remove the head itself (when the list has exactly n nodes), we would need special-case logic. The dummy node ensures there is always a predecessor node, making the removal logic uniform for every case.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5], n = 2:

Step 1: Create a dummy node pointing to head. Both fast and slow start at dummy.

  • dummy → 1 → 2 → 3 → 4 → 5 → null
  • fast = dummy, slow = dummy

Step 2: Advance fast by 1 step (step 1 of n=2): fast moves to node 1.

Step 3: Advance fast by 1 more step (step 2 of n=2): fast moves to node 2. Now there is a gap of 2 nodes between slow (at dummy) and fast (at node 2).

Step 4: Move both together. fast.next is node 3 (not null), so we continue.

  • slow moves to node 1, fast moves to node 3.

Step 5: fast.next is node 4 (not null), so we continue.

  • slow moves to node 2, fast moves to node 4.

Step 6: fast.next is node 5 (not null), so we continue.

  • slow moves to node 3, fast moves to node 5.

Step 7: fast.next is null. Stop! slow is at node 3, which is the predecessor of node 4 (our target).

Step 8: Remove node 4 by setting slow.next = slow.next.next (node 3 now points to node 5).

Step 9: Return dummy.next = node 1. Result: [1, 2, 3, 5].

Two Pointers — One Pass Removal — Watch how the fast pointer races ahead by n steps, then both pointers advance together until fast reaches the end, naturally positioning slow at the predecessor of the target node.

Algorithm

  1. Create a dummy node and set dummy.next = head
  2. Initialize two pointers, slow and fast, both pointing to dummy
  3. Advance the fast pointer n steps forward (this creates a gap of n between the two pointers)
  4. Move both slow and fast forward one step at a time until fast.next becomes null
  5. When the loop ends, slow is at the predecessor of the target node
  6. Remove the target: slow.next = slow.next.next
  7. Return dummy.next as the head of the modified list

Code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        
        // Advance fast pointer n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
        
        // Move both until fast reaches the last node
        while (fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }
        
        // Remove the target node
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;
        delete toDelete;
        
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow = dummy
        fast = dummy
        
        # Advance fast pointer n steps ahead
        for _ in range(n):
            fast = fast.next
        
        # Move both until fast reaches the last node
        while fast.next:
            slow = slow.next
            fast = fast.next
        
        # Remove the target node
        slow.next = slow.next.next
        
        return dummy.next
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        // Advance fast pointer n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        
        // Move both until fast reaches the last node
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Remove the target node
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(L)

We traverse the linked list exactly once. The fast pointer is advanced n steps initially, then both pointers move together until fast reaches the end. The total number of pointer moves is L (where L is the length of the list). Unlike the brute force approach, we never revisit any node.

Space Complexity: O(1)

We use only a constant amount of extra space: the dummy node and two pointers (slow and fast). No additional memory proportional to the input size is required.