Recursively delete the nth node of a linked list

You're working through a linked list problem set when you encounter a twist: instead of the usual iterative pointer manipulation, the problem asks you to delete a node recursively. This forces you to think about the list differently. Rather than walking through with a loop and tracking a previous pointer, you let the call stack do the tracking for you. It is a small shift in perspective, but one that unlocks a clean and elegant solution.

TL;DR

To recursively delete the nth node (zero-indexed) from a linked list, use two base cases: return null if the list is empty, and return head.next if n == 0 (skipping the current node). For the recursive case, set head.next to the result of calling deleteAtIndex(head.next, n - 1), then return head. This runs in O(n) time and O(n) space due to the recursion stack.

Why This Problem Matters

Recursive linked list manipulation is a core interview pattern. Once you understand how to delete a node recursively, the same technique applies to inserting nodes, reversing sublists, and merging lists. The real skill being tested here is not the deletion itself, but whether you can think recursively about a linear data structure. Companies use problems like this to gauge your comfort with the call stack and your ability to express solutions without explicit loops.

Linked Lists: The Basics

A linked list is a chain of nodes where each node holds some data and a pointer to the next node. Unlike arrays, there is no random access. To reach the nth element, you must start at the head and walk forward n steps.

In Firecode's ListNode interface, each node exposes a data field and a next pointer. The last node's next is null, marking the end of the list.

Understanding the Problem

Given the head of a linked list and a zero-indexed position n, delete the node at position n and return the modified list's head. If n is out of bounds, return the list unchanged.

Here is the transformation for deleteAtIndex(head, 3) on the list [1, 2, 3, 4, 5]:

Before (node 4 at index 3 is highlighted):

After (node 4 removed, node 3 now points to node 5):

Edge Cases

1. Null head: The list is empty, return null
2. n = 0: Delete the head itself, return head.next
3. n at the last index: Delete the tail, previous node's next becomes null
4. n out of bounds: Recursion hits null before n reaches 0, list stays unchanged

Solution Approach

The recursive insight is this: you do not need to track a "previous" pointer like in the iterative approach. Instead, each recursive call handles one node. If the current node is the target (n == 0), skip it by returning head.next. Otherwise, recurse on the rest of the list with n - 1 and reconnect the current node's next to whatever comes back.

Think of it like a relay race. Each node passes the message "delete the node at position n" down the chain, decrementing n by 1 at each step. When n hits 0, that node knows it is the target and removes itself by returning its successor.

Tracing Through an Example

Let's trace deleteAtIndex(head, 1) on the list [A, B, C]:

Call 1: At node A, n = 1. Not the target. Recurse on B with n = 0.

Call 2: At node B, n = 0. This is the target. Return B.next (node C).

Unwinding Call 1: Back at node A, set A.next = C (the return value from Call 2). Return A.

The deletion happens through pointer reassignment as the call stack unwinds. No explicit "previous" tracking needed.

Implementation

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

public class Solution {
  public ListNode deleteAtIndex(ListNode head, int n) {
    // Base case: empty list
    if (head == null) {
      return null;
    }

    // Base case: found the node to delete
    if (n == 0) {
      return head.next;
    }

    // Recursive case: move to next node with decremented index
    head.next = deleteAtIndex(head.next, n - 1);

    return head;
  }
}

Let's walk through each piece:

1. Null check: If head is null, there is nothing to delete. This also handles the case where n exceeds the list length, because the recursion eventually reaches a null node.

2. Target found: When n == 0, the current node is the one to delete. Returning head.next skips the current node entirely. The caller will wire this return value into the previous node's next pointer.

3. Recurse deeper: For all other nodes, recurse on head.next with n - 1. The critical line is head.next = deleteAtIndex(head.next, n - 1). This reassignment is what actually performs the deletion during unwinding. For non-target nodes, it simply reconnects the same pointer. For the parent of the target, it reconnects to the node after the target.

The Recursion Stack Visualized

For deleteAtIndex(head, 3) on [1, 2, 3, 4, 5]:

Call 1: node 1, n=3, not target, recurse

Call 2: node 2, n=2, not target, recurse

Call 3: node 3, n=1, not target, recurse

Call 4: node 4, n=0, target found! Return node 5

As the stack unwinds: Call 3 sets node 3's next to node 5. Calls 2 and 1 reconnect unchanged pointers. The final result is [1, 2, 3, 5].

Special Cases in Action

Deleting the Head (n = 0)

When n is 0, no recursion is needed at all. The function returns head.next immediately:

Result:

Out-of-Bounds Index

If n = 3 on a list with only 2 elements like [1, 2], the recursion walks past node 2 and hits null. The null base case returns null, and the stack unwinds reconnecting every pointer exactly as it was. The list comes back unchanged.

Complexity Analysis

Time Complexity: O(n)

Each recursive call processes one node, and we make at most n + 1 calls (where n is the index to delete, or the list length if out of bounds). Each call does O(1) work: a comparison, a pointer reassignment, and a return.

Space Complexity: O(n)

The recursion depth equals the number of calls before hitting a base case. In the worst case (deleting the last node or an out-of-bounds index), this equals the list length. Each stack frame consumes constant space, so total stack usage is O(n).

This is the key tradeoff versus iteration. An iterative solution achieves the same O(n) time with O(1) space by using a loop and a previous-pointer variable. Mention this tradeoff in your interview to show you understand the cost of recursion.

Common Pitfalls

1. Forgetting to reassign head.next: Writing deleteAtIndex(head.next, n - 1) without storing the result back into head.next means the deletion never takes effect. The recursive call returns the correct modified sublist, but nobody wires it in.

2. Missing the null base case: Without checking head == null, an out-of-bounds index causes a NullPointerException. Both base cases are necessary.

3. Returning null instead of head: The last line must return head, not null. Returning null would disconnect the entire list from the current node onward.

4. Off-by-one with indexing convention: This problem uses zero-indexed positions. If your interviewer expects one-indexed, adjust the n == 0 check to n == 1. Always clarify before coding.

Interview Tips

When solving this in an interview:

1. Clarify the indexing: "Is n zero-indexed or one-indexed?" This changes when you hit the base case.

2. State the base cases first: "I need two base cases: null head and n equals zero." Starting with base cases is the standard way to structure any recursive solution.

3. Draw the pointer reassignment: Sketch three nodes and show how head.next = deleteAtIndex(head.next, n-1) works during unwinding. This demonstrates you understand the mechanism, not just the code.

4. Mention the space tradeoff: "This uses O(n) stack space. An iterative approach would use O(1) space but require tracking a previous pointer." Interviewers love hearing you weigh alternatives.

5. Consider follow-ups: You might be asked to delete all nodes with a given value, delete the nth node from the end, or convert the solution to iterative. Having the recursive version solid makes these extensions straightforward.

Summing Up

• Two base cases drive the solution: null head returns null, n == 0 returns head.next to skip the target node.
• The recursive case head.next = deleteAtIndex(head.next, n - 1) delegates deletion to deeper calls and reconnects pointers on the way back up.
• Time is O(n), space is O(n) due to the call stack. An iterative approach saves space but requires explicit previous-pointer tracking.
• Out-of-bounds indices are handled naturally: the recursion hits null before n reaches 0, leaving the list unchanged.
• Always clarify zero-indexed vs. one-indexed with your interviewer before writing code.

Related Problems

Once you are comfortable with recursive node deletion, try these to deepen your linked list and recursion skills:

• Delete the head node of a linked list - the simplest deletion, good for warming up
• Delete the nth node from the end - requires two passes or the two-pointer technique
• Reverse a linked list recursively - the same recursive thinking applied to reversal
• Merge two sorted linked lists - recursive merge is another classic

This problem and hundreds of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. Whether you are just starting out or sharpening your skills for a specific interview, consistent practice with problems like this builds the pattern recognition that makes interview day feel routine.

Solutions in Other Languages

Python

class Solution:
    def delete_at_index(self, head, n):
        if head is None:
            return None

        if n == 0:
            return head.next

        head.next = self.delete_at_index(head.next, n - 1)

        return head

JavaScript

class Solution {
  deleteAtIndex(head, n) {
    if (head === null) {
      return null;
    }

    if (n === 0) {
      return head.next;
    }

    head.next = this.deleteAtIndex(head.next, n - 1);

    return head;
  }
}

TypeScript

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

    if (n === 0) {
      return head.next;
    }

    head.next = this.deleteAtIndex(head.next, n - 1);

    return head;
  }
}

C++

The C++ version includes proper memory management by freeing the deleted node:

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

    if (n == 0) {
      ListNode* temp = head->next;
      delete head;
      return temp;
    }

    head->next = deleteAtIndex(head->next, n - 1);

    return head;
  }
};

Scala

class Solution {
  def deleteAtIndex(head: ListNode, n: Int): ListNode = {
    if (head == null) return null

    if (n == 0) return head.next

    head.next = deleteAtIndex(head.next, n - 1)

    head
  }
}

Kotlin

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

        if (n == 0) {
            return head.next
        }

        head.next = deleteAtIndex(head.next, n - 1)

        return head
    }
}

Ruby

class Solution
  def delete_at_index(head, n)
    return nil if head.nil?

    return head.next if n == 0

    head.next = delete_at_index(head.next, n - 1)

    head
  end
end

Swift

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

        if n == 0 {
            return head?.next
        }

        head?.next = deleteAtIndex(head?.next, n - 1)

        return head
    }
}

Rust

impl Solution {
    pub fn delete_at_index(&self, head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        if head.is_none() {
            return None;
        }

        if n == 0 {
            return head.unwrap().next;
        }

        let mut node = head.unwrap();
        node.next = self.delete_at_index(node.next, n - 1);

        Some(node)
    }
}

C#

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

        if (n == 0) {
            return head.next;
        }

        head.next = DeleteAtIndex(head.next, n - 1);

        return head;
    }
}

Dart

class Solution {
  ListNode? deleteAtIndex(ListNode? head, int n) {
    if (head == null) {
      return null;
    }

    if (n == 0) {
      return head.next;
    }

    head.next = deleteAtIndex(head.next, n - 1);

    return head;
  }
}

PHP

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

        if ($n === 0) {
            return $head->next;
        }

        $head->next = $this->deleteAtIndex($head->next, $n - 1);

        return $head;
    }
}