19. Remove Nth Node From End of List - Explanation

Description

You are given the beginning of a linked list head, and an integer n.

Remove the nth node from the end of the list and return the beginning of the list.

Example 1:

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

Output: [1,2,4]

Example 2:

Input: head = [5], n = 1

Output: []

Example 3:

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

Output: [2]

Constraints:

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

Recommended Time & Space Complexity

You should aim for a solution with O(N) time and O(1) space, where N is the length of the given list.

Hint 1

A brute force solution would involve storing the nodes of the list into an array, removing the nth node from the array, and then converting the array back into a linked list to return the new head. However, this requires O(N) extra space. Can you think of a better approach to avoid using extra space? Maybe you should first solve with a two pass approach.

Hint 2

We can use a two-pass approach by first finding the length of the list, N. Since removing the nth node from the end is equivalent to removing the (N - n)th node from the front, as they both mean the same. How can you remove the node in a linked list?

Hint 3

For example, consider a three-node list [1, 2, 3]. If we want to remove 2, we update the next pointer of 1 (initially pointing to 2) to point to the node after 2, which is 3. After this operation, the list becomes [1, 3], and we return the head. But, can we think of a more better approach? Maybe a greedy calculation can help.

Hint 4

We can solve this in one pass using a greedy approach. Move the first pointer n steps ahead. Then, start another pointer second at the head and iterate both pointers simultaneously until first reaches null. At this point, the second pointer is just before the node to be removed. We then remove the node that is next to the second pointer. Why does this work?

Hint 5

This greedy approach works because the second pointer is n nodes behind the first pointer. When the first pointer reaches the end, the second pointer is exactly n nodes from the end. This positioning allows us to remove the nth node from the end efficiently.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

We store all nodes in an array so we can directly access the node that is n positions from the end.
Once we know which node to delete, we simply adjust the next pointer of the previous node.

Algorithm

Traverse the linked list and push every node into an array.
Compute the index of the node to remove: len(nodes) - n.
If this index is 0, it means the head must be removed → return head.next.
Otherwise, connect nodes[removeIndex - 1].next to nodes[removeIndex].next.
Return the updated head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next

        removeIndex = len(nodes) - n
        if removeIndex == 0:
            return head.next

        nodes[removeIndex - 1].next = nodes[removeIndex].next
        return head

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(N)$

2. Iteration (Two Pass)

Intuition

We first count how many nodes are in the list.
Once we know the total length, the node to delete is at position N - n from the start.
We run a second pass to reach the node just before it and skip it.

Algorithm

Traverse the list once to compute total nodes N.
Compute removeIndex = N - n.
If removeIndex == 0, delete the head → return head.next.
Traverse again until reaching the node before removeIndex.
Update its next pointer to skip the unwanted node.
Return the modified head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        N = 0
        cur = head
        while cur:
            N += 1
            cur = cur.next

        removeIndex = N - n
        if removeIndex == 0:
            return head.next

        cur = head
        for i in range(N - 1):
            if (i + 1) == removeIndex:
                cur.next = cur.next.next
                break
            cur = cur.next
        return head

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(1)$

3. Recursion

Intuition

Recursion naturally processes the list from the end toward the start.
When the recursive calls unwind, we count backwards.
When the count reaches the nth node from the end, we skip it by returning head.next instead of the current node.

Algorithm

Recursively go to the end of the list.
As recursion unwinds, decrement n each time you return.
When n becomes 0, this is the node to delete → return its next node.
Otherwise, return the current node to rebuild the list.
The head of the resulting rebuilt list is the final answer.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def rec(self, head, n):
        if not head:
            return None

        head.next = self.rec(head.next, n)
        n[0] -= 1
        if n[0] == 0:
            return head.next
        return head

    def removeNthFromEnd(self, head, n):
        return self.rec(head, [n])

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(N)$ for recursion stack.

4. Two Pointers

Intuition

Use two pointers so that the gap between them is exactly n.
Move the right pointer n steps ahead first.
Then move both pointers together.
When the right pointer reaches the end, the left pointer will be just before the node we must remove.
This avoids counting the entire list and removes the target in one pass.

Algorithm

Create a dummy node pointing to the head (helps handle deletion of the first node).
Set two pointers:
- left at dummy
- right at head
Move right forward n steps.
Move both pointers until right reaches the end.
Now left.next is the node to delete → skip it by doing left.next = left.next.next.
Return dummy.next as the updated head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        left = dummy
        right = head

        while n > 0:
            right = right.next
            n -= 1

        while right:
            left = left.next
            right = right.next

        left.next = left.next.next
        return dummy.next

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Handle Head Removal

When n equals the length of the list, the head node itself must be removed. Without a dummy node or explicit check for this case, the code may crash or return incorrect results. Always verify your solution works when the target is the first node.

Off-by-One Errors in Pointer Positioning

The two-pointer technique requires the left pointer to stop at the node before the one to delete. A common mistake is advancing right by n-1 instead of n steps, causing the wrong node to be removed. Carefully trace through a small example to confirm your gap is correct.

Not Returning the Updated Head

After modifying the list, forgetting to return dummy.next (or the updated head) results in returning a stale reference. This is especially problematic when the original head was deleted. Always ensure your return statement reflects any structural changes to the list.