Insert Node

Insert a new node holding value at position index (0-based) and return the head. Index 0 inserts at the front. If index is at or beyond the list length, append at the end.

insertNode(head, index, value)

Input format: list | index | value. Output the resulting list, space-separated.

Examples

(1 → 2 → 3), index 1, value 9   // → 1 → 9 → 2 → 3
(1 → 2 → 3), index 0, value 9   // → 9 → 1 → 2 → 3
(1 → 2 → 3), index 5, value 9   // → 1 → 2 → 3 → 9

Walkthrough

Thinking it through

Inserting a node has the same structural challenge as removing one: to splice a new node in before a position, you need a handle on the node that will sit just before it. And just like removal, inserting at position zero has no natural predecessor within the original list — another case for a dummy node.

Reusing the dummy-head idea

Placing a placeholder before the real head means position zero stops being special: inserting "before the original head" becomes the same operation as inserting after any other node — right after the dummy. The walk-to-position-then-splice logic stays uniform regardless of whether the target is the front, the middle, or past the end.

Building the approach

Create the dummy pointing at the original head, and start "previous" there.
Walk "previous" forward once per unit of the target index, so it ends up on the node that should come right before the new one.
Add a safety condition: if the list is shorter than the requested index, stop early once "previous" has no next node left. This is what makes "insert past the end" gracefully become "append at the end," with no separate append routine needed.
Create the new node.
Splice it in: point the new node's next at previous.next first — before touching previous.next — then point previous.next at the new node.
Return the dummy's next.

Why the order of the two pointer assignments matters

If you set previous.next to the new node before wiring the new node's own next, you'd overwrite your only reference to the rest of the list, losing everything after the insertion point. Wiring the new node's outgoing pointer first, while the old chain is still intact, is what makes the splice safe.

Why this handles every edge case uniformly

Inserting into an empty list, at the front, in the middle, or past the end are all, mechanically, "walk previous some number of steps (possibly zero, possibly capped by running out of list), then splice." No case needs bespoke logic.

Why this is efficient

The walk touches at most index nodes (or the whole list, if the index exceeds it), so work is linear in the requested position, with only a small constant number of pointers needed regardless of list size.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.