Insert a node in a linked list at a specific index

You're midway through a Pivotal interview, and the interviewer slides a diagram across the table showing a chain of connected nodes. "Suppose you have this linked list," they say, "and I need you to insert a new value at a specific position. How would you handle all the edge cases?" This problem, also known as "Insert at Index in Linked List" on other platforms, tests your ability to manipulate pointers precisely while keeping your code clean and edge-case-free. It's a favorite at companies like Pivotal, TripAdvisor, and Firecode because it reveals whether you truly understand how linked list pointers work under the hood.

TL;DR

Insert a node at a zero-indexed position in a singly linked list by using a sentinel (dummy) node to unify all edge cases. Create the sentinel pointing to head, traverse to the node just before the target index, then splice in the new node by updating two pointers. If the index exceeds the list length, append at the end. This runs in O(n) time and O(1) space. The sentinel node eliminates the need for separate head-insertion logic, making the code concise and less error-prone.

Why This Problem Matters

Linked list insertion at a specific index is a step up from basic head or tail insertion. It forces you to handle traversal, boundary conditions, and pointer rewiring all in one method. I've seen this problem trip up candidates who can reverse a linked list but stumble when they need to insert at an arbitrary position, especially at index 0 or beyond the list's length. Master this, and you'll have a solid foundation for more complex linked list operations like splicing sublists, implementing LRU caches, or building skip lists.

Linked Lists: A Quick Refresher

A singly linked list is a sequence of nodes where each node holds a value and a reference to the next node. Unlike arrays, there's no random access. You have to walk from the head to reach any position.

Key properties:

• Head: The first node in the list
• Tail: The last node, whose next points to null
• Sequential access: Reaching index i requires traversing i nodes from the head
• Efficient insertion: Once you're at the right position, inserting is a constant-time pointer update

Understanding the Problem

Here's what we need to do:

Given: The head of a singly linked list, an integer n, and a zero-indexed integer i Task: Insert a new node with data n at index i Return: The head of the modified list Constraint: If i exceeds the list length, insert at the end. Aim for O(1) space.

Consider the linked list [1, 2, 3] with head pointing to the node containing 1:

insertAtIndex(head, -1, 0) -> [-1, 1, 2, 3]
insertAtIndex(head, -1, 1) -> [1, -1, 2, 3]
insertAtIndex(head, -1, 2) -> [1, 2, -1, 3]
insertAtIndex(head, -1, 3) -> [1, 2, 3, -1]

Inserting at the front (index 0):

The new node becomes the new head, and the old head follows.

Inserting in the middle (index 2):

The new node is spliced between the nodes that were at positions 1 and 2.

Inserting at the end (index 3, which equals the list length):

The new node is appended at the tail.

Edge Cases to Consider

1. Null head (empty list): The new node becomes the only element
2. Index 0: Inserting at the front, new node becomes head
3. Index equals list length: Appending at the end
4. Index exceeds list length: Also append at the end (per the problem spec)
5. Single-element list: Must handle both index 0 and index 1 correctly

Solution Approach

The naive approach involves writing separate logic for inserting at the head versus inserting elsewhere. That leads to branching code and is easy to get wrong. There's a cleaner way.

The Sentinel Node Trick

A sentinel node (also called a dummy node) is a placeholder that sits before the actual head of the list. It doesn't hold meaningful data, but it guarantees that every real node has a predecessor. This eliminates the special case for index 0.

The node labeled "S" is the sentinel. It points to the real head (node 1). By starting our traversal at the sentinel, we can treat all insertion positions uniformly: traverse to the node just before the target index, then splice in the new node.

Building the Algorithm

Let's walk through inserting -1 at index 2 in the list [1, 2, 3]:

Step 1: Create sentinel and position the iterator

Create a sentinel node pointing to head. Set previous to the sentinel.

The sentinel (S) is highlighted. Our previous pointer starts here.

Step 2: Traverse to the insertion point

Decrement i and advance previous until we've moved i positions or reached the end.

After two iterations, previous points to node 2 (highlighted). This is the node just before our target index.

Step 3: Splice in the new node

Create a new node with value -1. Set its next to previous.next (node 3), then set previous.next to the new node.

The new node -1 (highlighted) is now between nodes 2 and 3.

Step 4: Return sentinel.next

The sentinel's next pointer gives us the true head of the modified list.

Final result: [1, 2, -1, 3].

Implementation

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

Here's the Java solution using the sentinel node approach:

public class Solution {
  public ListNode insertAtIndex(ListNode head, int n, int i) {
    // Create a sentinel dummy node pointing to head
    ListNode sentinelNode = new ListNode(Integer.MIN_VALUE, head);

    // Start traversal from the sentinel
    ListNode previous = sentinelNode;

    // Traverse to the node just before the target index
    // Stop early if we reach the end of the list
    while (--i >= 0 && previous.next != null) {
      previous = previous.next;
    }

    // Insert the new node: it points to whatever previous was pointing to
    previous.next = new ListNode(n, previous.next);

    // Return the real head (skip the sentinel)
    return sentinelNode.next;
  }
}

Let's trace through this with insertAtIndex([1,2,3,4,5], -1, 3):

Iteration 1:

• --i makes i = 2, condition 2 >= 0 is true, previous.next is node 1 (not null)
• previous moves from sentinel to node 1

Iteration 2:

• --i makes i = 1, condition 1 >= 0 is true, previous.next is node 2 (not null)
• previous moves from node 1 to node 2

Iteration 3:

• --i makes i = 0, condition 0 >= 0 is true, previous.next is node 3 (not null)
• previous moves from node 2 to node 3

Loop exits because the next --i gives -1, failing the >= 0 check.

Now previous is at node 3. We create a new node with data -1, pointing to previous.next (node 4). Then previous.next is updated to point to the new node. Result: [1, 2, 3, -1, 4, 5].

Why Pre-Decrement Matters

The --i pre-decrement is a subtle but important detail. It decrements i before the comparison, so the loop runs exactly i times. If we used i-- (post-decrement), we'd check the old value first, causing previous to end up one position too far. This is the kind of off-by-one detail interviewers love to probe.

Handling Edge Cases

Null head:

When head is null, the sentinel points to null. The while loop's previous.next != null check fails immediately, so the new node is inserted right after the sentinel. Returning sentinelNode.next gives us the new node as head.

Index exceeds length:

For insertAtIndex([1], -1, 5), the loop advances previous from sentinel to node 1, then previous.next becomes null, ending the loop early. The new node is appended at the end.

Complexity Analysis

Time Complexity: O(n)

We traverse at most min(i, length) nodes to reach the insertion point. In the worst case (index equals or exceeds list length), we traverse the entire list. The actual insertion is O(1), just two pointer updates.

Space Complexity: O(1)

We use a fixed number of variables: the sentinel node, the previous pointer, and the new node. No auxiliary data structures, no recursion. This meets the problem's constant-space constraint.

Comparison with Array Insertion

Inserting into an array at index i requires shifting all elements from i onward, making it O(n) for the shift. Linked list insertion avoids this shifting cost entirely. The tradeoff is the O(i) traversal to reach the position, since linked lists don't support random access.

Common Pitfalls

Here are the mistakes I see candidates make most often with this problem:

1. Forgetting the head-insertion case: Without a sentinel, inserting at index 0 requires returning the new node as head. Many candidates forget this and return the old head.

   // Wrong - doesn't handle index 0
   ListNode current = head;
   for (int j = 0; j < i - 1; j++) { current = current.next; }
   current.next = new ListNode(n, current.next); // Crashes at i=0
   return head; // Wrong head if i was 0
   

2. Off-by-one in traversal: Ending up one node too far or too short. The sentinel approach avoids this because you always traverse exactly i hops from the sentinel.

3. Not handling null head: If head is null and you try to access head.next, you'll get a NullPointerException. The sentinel node sidesteps this entirely.

4. Ignoring the "index exceeds length" case: The problem says to insert at the end. Without the previous.next != null check in the loop, you'd walk past the tail and crash.

Interview Tips

When solving this problem in an interview:

1. Start with clarifying questions:

   • "What should happen if the index is larger than the list length?"
   • "Can the head be null?"
   • "Is the index always non-negative?"

2. Mention the sentinel node upfront: Telling your interviewer "I'll use a sentinel node to handle edge cases uniformly" demonstrates experience with linked list patterns.

3. Draw the pointer updates: Sketch the before and after states of the previous.next reassignment. This shows clear thinking and catches bugs before you code.

4. Walk through edge cases after coding: Trace through index 0, index equal to length, null head, and a normal middle insertion.

5. Discuss tradeoffs: If asked about alternatives, mention that you could handle the head case separately with an if-check, but the sentinel approach is cleaner and less error-prone.

Key Takeaways

• The sentinel (dummy) node pattern eliminates special-case logic for head insertion, producing cleaner and more reliable code.
• Pre-decrement (--i) in the loop condition ensures exactly i traversal hops from the sentinel to the node just before the target index.
• The dual loop condition --i >= 0 && previous.next != null handles both normal insertion and the "index exceeds length" case in a single loop.
• Linked list insertion at a known position is O(1) for the pointer update itself. The O(n) cost comes from the traversal to reach that position.
• Always trace through null head, index 0, and index-exceeds-length as your three validation cases before declaring a linked list solution correct.

Practice and Related Problems

Once you've nailed insertion at a specific index, these related problems will reinforce your linked list pointer skills:

• Insert a node at the front of a linked list (the simplest insertion case)
• Insert a node at the end of a linked list (tail insertion)
• Delete the Nth node of a linked list (similar traversal, different pointer update)
• Reverse a linked list (the gold-standard pointer manipulation problem)

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed jobs at top tech companies. Whether you're just starting out or ramping up for a FAANG interview, mastering linked list fundamentals like this will set you apart.

Solutions in Other Languages

Python

class Solution:
    def insert_at_index(self, head, n, i):
        sentinel_node = ListNode(-1, head)
        previous = sentinel_node
        while i > 0 and previous.next is not None:
            previous = previous.next
            i -= 1
        previous.next = ListNode(n, previous.next)
        return sentinel_node.next

JavaScript

class Solution {
  insertAtIndex(head, n, i) {
    const sentinelNode = new ListNode(Number.NEGATIVE_INFINITY, head);
    let previous = sentinelNode;
    while (--i >= 0 && previous.next !== null) {
      previous = previous.next;
    }
    previous.next = new ListNode(n, previous.next);
    return sentinelNode.next;
  }
}

TypeScript

class Solution {
  insertAtIndex(head: ListNode | null, n: number, i: number): ListNode | null {
    const sentinelNode = new ListNode(Number.NEGATIVE_INFINITY, head);
    let previous: ListNode | null = sentinelNode;
    while (--i >= 0 && previous.next !== null) {
      previous = previous.next;
    }
    previous.next = new ListNode(n, previous.next);
    return sentinelNode.next;
  }
}

C++

class Solution {
public:
  ListNode* insertAtIndex(ListNode* head, int n, int i) {
    ListNode* sentinelNode = new ListNode(INT_MIN, head);
    ListNode* previous = sentinelNode;
    while (--i >= 0 && previous->next != nullptr) {
      previous = previous->next;
    }
    previous->next = new ListNode(n, previous->next);
    return sentinelNode->next;
  }
};

Scala

class Solution {
  def insertAtIndex(head: ListNode, n: Int, i: Int): ListNode = {
    val sentinelNode = ListNode(Int.MinValue, head)
    var previous = sentinelNode
    var counter = i
    while (counter > 0 && previous.next != null) {
      previous = previous.next
      counter -= 1
    }
    previous.next = ListNode(n, previous.next)
    sentinelNode.next
  }
}

Kotlin

class Solution {
  fun insertAtIndex(head: ListNode?, n: Int, i: Int): ListNode? {
    val sentinelNode = ListNode(Int.MIN_VALUE, head)
    var previous = sentinelNode
    var index = i
    while (--index >= 0 && previous.next != null) {
      previous = previous.next!!
    }
    previous.next = ListNode(n, previous.next)
    return sentinelNode.next
  }
}

Ruby

class Solution
  def insert_at_index(head, n, i)
    sentinel_node = ListNode.new(-Float::INFINITY, head)
    previous = sentinel_node
    i -= 1
    while i >= 0 && !previous.next.nil?
      previous = previous.next
      i -= 1
    end
    previous.next = ListNode.new(n, previous.next)
    sentinel_node.next
  end
end

Rust

pub fn insert_at_index(&self, head: Option<Box<ListNode>>, n: i32, i: i32) -> Option<Box<ListNode>> {
    let mut sentinel = Box::new(ListNode::with_next(i32::MIN, head));
    let mut previous = &mut *sentinel;
    let mut idx = i;
    while idx > 0 && previous.next.is_some() {
        previous = previous.next.as_mut().unwrap();
        idx -= 1;
    }
    previous.next = Some(Box::new(ListNode::with_next(n, previous.next.take())));
    sentinel.next
}

Swift

class Solution {
    func insertAtIndex(_ head: ListNode?, _ n: Int, _ i: Int) -> ListNode? {
        let sentinelNode = ListNode(Int.min, head)
        var previous: ListNode? = sentinelNode
        var index = i
        while index > 0 && previous?.next != nil {
            index -= 1
            previous = previous?.next
        }
        previous?.next = ListNode(n, previous?.next)
        return sentinelNode.next
    }
}

Dart

ListNode? insertAtIndex(ListNode? head, int n, int i) {
    ListNode sentinelNode = ListNode(0, head);
    ListNode? previous = sentinelNode;
    int index = i;
    while (index > 0 && previous?.next != null) {
      previous = previous?.next;
      index -= 1;
    }
    previous?.next = ListNode(n, previous?.next);
    return sentinelNode.next;
}

C#

public ListNode? insertAtIndex(ListNode? head, int n, int i) {
    var sentinelNode = new ListNode(int.MinValue, head);
    ListNode previous = sentinelNode;
    while (--i >= 0 && previous.next != null) {
        previous = previous.next;
    }
    previous.next = new ListNode(n, previous.next);
    return sentinelNode.next;
}

PHP

public function insertAtIndex(?ListNode $head, int $n, int $i): ?ListNode {
    $sentinelNode = new ListNode(PHP_INT_MIN, $head);
    $previous = $sentinelNode;
    while (--$i >= 0 && $previous->next !== null) {
        $previous = $previous->next;
    }
    $previous->next = new ListNode($n, $previous->next);
    return $sentinelNode->next;
}