Remove Nth Node from end of List

Problem Link

19. Remove Nth Node From End of List – LeetCode

Problem Statement

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

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Constraints

• The number of nodes in the list is sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

Intuition

To remove the nth node from the end, we first need to identify its position from the start.
We do this in two passes:

1. Count the total number of nodes.

2. Subtract n from total size to get the position from the start.

3. Traverse again and remove the node at that position.

Approach (Two-Pass)

1. Traverse the list to get the total size.

2. Subtract n from size to get the position from the beginning.

3. If that position is 0, return head.next (removing the first node).

4. Otherwise, iterate again to that position and skip the node.

5. Return the modified head.

Java Code

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int size = 0;
        ListNode curr = head;

        // Count total nodes
        while (curr != null) {
            size++;
            curr = curr.next;
        }

        size -= n;

        // If we need to remove the head node
        if (size == 0) return head.next;

        curr = head;
        // Traverse to the node before the one to remove
        while (size > 1) {
            curr = curr.next;
            size--;
        }

        // Remove the target node
        curr.next = curr.next.next;

        return head;
    }
}

Time and Space Complexity

Dry Run

Input:

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

Steps:

1. Count nodes: 5

2. Position from start = 5 - 2 = 3

3. Traverse to 3rd node (node.val = 3)

4. Set node.next = node.next.next, i.e., 4 → 5 becomes 4 → 5 → null

Output: [1, 2, 3, 5]

Follow-Up: One-Pass Solution (Optional)

Use two pointers first and second with a gap of n between them. When first reaches the end, second will be just before the node to be removed. This allows solving the problem in a single pass.

Conclusion

This problem is a classic example of pointer manipulation in singly linked lists. While the two-pass method is intuitive, it sets the foundation for more optimized one-pass solutions using a two-pointer technique.