Add to a Linked List | Dataford Interview Questions

Accretive Technology Group services may need to insert an item at a specific position in an ordered in-memory list. Implement insertion into a singly linked list without converting it to a list.

Each node is represented as a two-element list: [value, next_node]. The next_node is another node or None. Given the head node, a value, and a valid zero-based index, insert a new node at that index and return the resulting head.

Formal Specification

Implement insert_at_index(head, value, index).

Input: head, a node represented as [value, next_node], or None; value, an integer; and index, a valid zero-based insertion position.
Output: The head node of the updated linked list.
The existing nodes must remain in their original order.
The operation must use linked-list pointer manipulation rather than rebuilding the list.

Constraints

0 <= index <= n, where n is the current list length
0 <= n <= 10^5
-10^9 <= value and existing node values <= 10^9
The input list is acyclic
The index is always valid

Function Signature

def insert_at_index(head, value, index):

Your question is Add to a Linked List. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem