Delete the nth node of a linked list

You're sitting in an Oracle technical interview, and the interviewer slides a sheet of paper across the table. "We have a linked list, and I need you to remove a node at a specific position. How would you approach that?" This is a bread-and-butter linked list problem that tests your comfort with pointer manipulation and edge case handling. It is also known as "Remove Nth Node From Linked List" on other platforms, and it shows up frequently in phone screens at companies like Oracle.

TL;DR

Traverse the linked list with two pointers: one tracking the current node and one tracking the previous node. When you reach the nth position, rewire previous.next to skip the target node. Handle n == 0 (head deletion) as a special case by returning head.next. If n exceeds the list length, return the list unchanged. This runs in O(n) time and O(1) space.

Why This Problem Matters

Deleting a node at a specific index is one of the fundamental linked list operations, alongside insertion and traversal. It forces you to think about edge cases that trip up many candidates: what if the list is empty? What if you're deleting the head? What if the index is out of bounds? Getting these right under pressure separates prepared candidates from everyone else.

Linked Lists Refresher

A singly linked list is a sequence of nodes where each node holds a value and a pointer to the next node. You can only traverse it in one direction, from head to tail.

The defining property of a singly linked list is that you cannot go backward. Once you pass a node, you have no way to return to it without starting over from the head. This constraint is exactly what makes deletion interesting.

Understanding the Problem

Here is what we need to do:

Given: The head node of a singly linked list and an integer n (zero-indexed) Task: Delete the node at index n and return the head of the modified list Constraints: If n is out of bounds, return the list unchanged. Use O(1) space.

For example, given the list [1, 2, 3, 4, 5] and n = 3:

We need to remove node 4 (at index 3) and produce:

The trick is that to delete node 4, we need to update node 3's next pointer to skip over 4 and point directly to 5. But since this is a singly linked list, we cannot access node 3 from node 4. We need to track the previous node as we go.

Prefer a different language? Jump to solutions in other languages.

Edge Cases to Consider

1. Empty list (null head): Return null
2. Deleting the head (n == 0): Return head.next
3. Single node list, n == 0: Return null
4. Index out of bounds (n ≥ list length): Return the list unchanged
5. Deleting the last node: previous.next becomes null

Solution Approach

The strategy is straightforward: walk through the list counting nodes until you reach position n, keeping track of the node just before it. Then rewire the pointers to skip the target node.

Special Case: Deleting the Head

When n == 0, there is no previous node to update. We simply return head.next:

After deleting the head:

The Two-Pointer Technique

For all other positions, we use two pointers:

• iterator: walks forward through the list
• previous: trails one step behind iterator

We advance both pointers n times. When the loop finishes, iterator sits at the node to delete, and previous sits right before it.

Walking Through an Example

Let's trace through deleting node at index 3 from [1, 2, 3, 4, 5]:

Initial state - iterator points to head (node 1), previous is a dummy node pointing to head:

After 1st iteration (n becomes 2) - both pointers advance. Iterator is at node 2:

After 2nd iteration (n becomes 1) - iterator is at node 3:

After 3rd iteration (n becomes 0) - iterator is at the target (node 4), previous is at node 3:

Now we set previous.next = iterator.next, which wires node 3 directly to node 5, effectively removing node 4 from the chain.

Implementation

Here is the full Java solution:

public class Solution {
  public ListNode deleteAtIndex(ListNode head, int n) {
    // Special case: deleting the head node
    if (n == 0) {
      return head == null ? null : head.next;
    }

    // Set up two pointers: iterator walks forward, previous trails behind
    ListNode iterator = head, previous = new ListNode(0, head);

    // Walk to the nth position
    while (iterator != null && n > 0) {
      previous = iterator;
      iterator = iterator.next;
      n--;
    }

    // Rewire: skip the target node (handles out-of-bounds gracefully)
    previous.next = iterator == null ? null : iterator.next;
    return head;
  }
}

A few things worth noting about this implementation:

1. The n == 0 guard handles head deletion cleanly. We check head == null to handle the edge case of deleting index 0 from an empty list.

2. The dummy node trick: We create previous = new ListNode(0, head), a dummy node whose next points to head. This gives previous a valid starting position without special-casing the first iteration.

3. Graceful out-of-bounds handling: If n exceeds the list length, the while loop exits because iterator becomes null before n reaches 0. The line previous.next = iterator == null ? null : iterator.next then sets previous.next to null, which is already its value at the end of the list. The original list is effectively unchanged.

Complexity Analysis

Time Complexity: O(n)

We traverse at most n nodes to reach the deletion point. In the worst case, we're deleting the last node, requiring a full traversal of the list. Each step does constant work (advancing pointers and decrementing a counter).

Space Complexity: O(1)

We use only a fixed number of pointer variables regardless of list size. The dummy previous node is a single allocation that doesn't scale with input size.

Why Not Recursion?

A recursive approach would work but uses O(n) stack space. Since the problem asks for O(1) space, the iterative two-pointer technique is the right choice.

Common Pitfalls

From reviewing hundreds of interview submissions, these mistakes come up repeatedly:

1. Forgetting the head deletion case: If you skip the n == 0 check, you will either fail to delete the head or corrupt the list by trying to access a non-existent previous node.

2. Not handling null lists: Calling head.next on a null head throws a NullPointerException. Always check for null before dereferencing.

3. Off-by-one errors in traversal: The counter n is zero-indexed. Getting confused about whether to stop when n == 0 or n == 1 leads to deleting the wrong node.

4. Returning the wrong head: After deleting the head, you must return head.next, not head. For all other deletions, return the original head.

Interview Tips

When you encounter this problem in an interview:

1. Clarify zero vs one indexing: Ask whether n starts at 0 or 1. This changes how you count during traversal.

2. Ask about edge cases upfront: "What should I return if the list is empty?" and "What if n is out of bounds?" Show the interviewer you think defensively.

3. Draw the pointers: Sketch a short list (3-4 nodes) and show how previous and iterator move. This catches off-by-one bugs before you write code.

4. Mention the dummy node approach: Some interviewers prefer a solution that uses a dummy head node to eliminate the n == 0 special case entirely. Mentioning this variant shows depth of knowledge.

5. Talk about trade-offs: "I could solve this recursively, but the iterative approach gives us O(1) space, which is better for large lists."

Related Patterns

This two-pointer traversal with a trailing previous pointer is a pattern you will see across many linked list problems:

• Reversing a linked list (previous tracks the reversed portion)
• Detecting and removing cycles (fast/slow pointers)
• Merging sorted lists (previous tracks the merged tail)

Once you internalize the pattern of "keep a reference to the node before the one you care about," a whole class of linked list problems becomes approachable.

Key Takeaways

• Always handle head deletion (n == 0) as a separate case, since there is no previous node to update.
• The two-pointer technique (iterator + previous) is the standard pattern for any linked list operation that needs to modify a node's predecessor.
• Check for null before accessing .next to avoid NullPointerException. This applies both to the head node and to the iterator after traversal.
• When n exceeds the list length, a well-written loop naturally terminates without modifying the list, so no extra bounds-checking code is needed.
• Interviewers value seeing you handle edge cases (empty list, single node, out of bounds) as much as the main logic.

Practice and Related Problems

Once you are comfortable with this problem, try these related challenges to solidify your linked list skills:

• Delete the head node of a linked list (the simplest deletion case)
• Delete the tail node of a linked list (no pointer to the predecessor)
• Remove the nth node from the end of a linked list (two-pointer gap technique)
• Reverse a linked list (same two-pointer structure, different operation)

This problem and hundreds of other linked list challenges are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. If you want to build real confidence with pointer manipulation problems, consistent practice is the fastest path.

Solutions in Other Languages

Python

class Solution:
    def delete_at_index(self, head: ListNode, n: int) -> ListNode:
        if n == 0:
            return None if head is None else head.next

        iterator, previous = head, ListNode(0, head)

        while iterator is not None and n > 0:
            previous = iterator
            iterator = iterator.next
            n -= 1

        previous.next = None if iterator is None else iterator.next
        return head

JavaScript

class Solution {
  deleteAtIndex(head, n) {
    if (n === 0) {
      return head === null ? null : head.next;
    }

    let iterator = head, previous = new ListNode(0, head);

    while (iterator !== null && n > 0) {
      previous = iterator;
      iterator = iterator.next;
      n--;
    }

    previous.next = iterator === null ? null : iterator.next;
    return head;
  }
}

TypeScript

class Solution {
  deleteAtIndex(head: ListNode | null, n: number): ListNode | null {
    if (n === 0) {
      return head === null ? null : head.next;
    }

    let iterator: ListNode | null = head, previous: ListNode = new ListNode(0, head);

    while (iterator !== null && n > 0) {
      previous = iterator;
      iterator = iterator.next;
      n--;
    }

    previous.next = iterator === null ? null : iterator.next;
    return head;
  }
}

C++

class Solution {
public:
  ListNode *deleteAtIndex(ListNode *head, int n) {
    if (n == 0) {
      return head == nullptr ? nullptr : head->next;
    }

    ListNode *iterator = head;
    ListNode *previous = new ListNode(0, head);

    while (iterator != nullptr && n > 0) {
      previous = iterator;
      iterator = iterator->next;
      n--;
    }

    previous->next = iterator == nullptr ? nullptr : iterator->next;

    if (iterator != nullptr) {
      delete iterator;
    }

    return head;
  }
};

Note that C++ requires explicit memory deallocation with delete to avoid memory leaks.

Scala

class Solution {
  def deleteAtIndex(head: ListNode, n: Int): ListNode = {
    if (n == 0) {
      return if (head == null) null else head.next
    }

    var iterator = head
    var previous = ListNode(0, head)
    var remainingSteps = n

    while (iterator != null && remainingSteps > 0) {
      previous = iterator
      iterator = iterator.next
      remainingSteps -= 1
    }

    previous.next = if (iterator == null) null else iterator.next
    head
  }
}

Scala uses an extra remainingSteps variable since function parameters are immutable by default.

Kotlin

class Solution {
    fun deleteAtIndex(head: ListNode?, n: Int): ListNode? {
        if (n == 0) {
            return head?.next
        }

        var iterator = head
        var previous = ListNode(0, head)
        var count = n

        while (iterator != null && count > 0) {
            previous = iterator
            iterator = iterator.next
            count--
        }

        previous.next = iterator?.next
        return head
    }
}

Kotlin's safe-call operator (?.) makes null handling more concise than Java.

Swift

class Solution {
    func deleteAtIndex(_ head: ListNode?, _ n: Int) -> ListNode? {
        if n == 0 {
            return head?.next
        }

        var iterator = head
        var previous: ListNode? = ListNode(0, head)
        var count = n

        while iterator != nil && count > 0 {
            previous = iterator
            iterator = iterator?.next
            count -= 1
        }

        previous?.next = iterator?.next
        return head
    }
}

Ruby

class Solution
  def delete_at_index(head, n)
    if n == 0
      return head.nil? ? nil : head.next
    end

    iterator, previous = head, ListNode.new(0, head)

    while iterator && n > 0
      previous = iterator
      iterator = iterator.next
      n -= 1
    end

    previous.next = iterator.nil? ? nil : iterator.next
    head
  end
end

Rust

pub fn delete_at_index(&self, head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
    if n == 0 {
        return head.and_then(|node| node.next);
    }

    let mut head = head;
    let mut count = n;
    let mut current = &mut head;

    while count > 1 {
        if let Some(ref mut node) = current {
            current = &mut node.next;
            count -= 1;
        } else {
            break;
        }
    }

    if let Some(ref mut node) = current {
        node.next = node.next.take().and_then(|deleted| deleted.next);
    }

    head
}

Rust's ownership model requires a different traversal strategy. Instead of tracking a separate previous pointer, we use mutable references to reach the node just before the target.

C#

public class Solution {
    public ListNode? DeleteAtIndex(ListNode? head, int n) {
        if (n == 0) {
            return head == null ? null : head.next;
        }

        ListNode? iterator = head, previous = new ListNode(0, head);

        while (iterator != null && n > 0) {
            previous = iterator;
            iterator = iterator.next;
            n--;
        }

        previous.next = iterator == null ? null : iterator.next;
        return head;
    }
}

Dart

ListNode? deleteAtIndex(ListNode? head, int n) {
    if (n == 0) {
      return head?.next;
    }

    ListNode? iterator = head;
    ListNode previous = ListNode(0, head);
    int count = n;

    while (iterator != null && count > 0) {
      previous = iterator!;
      iterator = iterator.next;
      count--;
    }

    previous.next = iterator?.next;
    return head;
}

PHP

class Solution {
    public function deleteAtIndex(?ListNode $head, int $n): ?ListNode {
        if ($n === 0) {
            return $head === null ? null : $head->next;
        }

        $iterator = $head;
        $previous = new ListNode(0, $head);

        while ($iterator !== null && $n > 0) {
            $previous = $iterator;
            $iterator = $iterator->next;
            $n--;
        }

        $previous->next = $iterator === null ? null : $iterator->next;
        return $head;
    }
}