Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Walk exactly position − 1 nodes to land on the node that will sit just before the new one, then do the two-line splice: newNode.next = prev.next; prev.next = newNode. Position 0 is the special case — there is no predecessor, so you insert at the head and return the new head. Everything else is O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can manipulate next pointers without losing the tail, count to the right predecessor (position − 1), and handle insertion at the head as a distinct case that changes the returned head.
Where candidates slip
Walking position steps instead of position − 1, or writing prev.next = newNode before newNode.next = prev.next and orphaning the rest of the list.
How to stand out
Call out the two invariants up front: stop one node early, and wire the new node's next before touching the predecessor's next. Mention that position 0 returns a new head, which is why the function returns a head at all.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewInsert node at 0-based positionposition == 0?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Iterative — Walk to Predecessor, Then Splice (Optimal)
1Hint 1Explore hintHide hint
To slip a node into index k, which existing node do you actually need a handle on — the one at k, or the one just before it?
2Hint 2Explore hintHide hint
Reaching index k − 1 means taking k − 1 steps from the head. What happens when k is 0 and there is no node before it?
3Hint 3Explore hintHide hint
Once you're standing on the predecessor, you need two links: the new node must point to what came after the predecessor, and the predecessor must point to the new node. Order those two assignments carefully.
A · Core idea
We reach the node directly before the target slot, then rewire two pointers to drop the new node in.
Why the predecessor, not the target. In a singly linked list you can only attach a node by editing some existing node's next. To put a node at index k, the node whose next must change is the one at index k − 1. So the whole job is: get a handle on the predecessor, then splice. That's why we walk position − 1 steps, not position.
Why position 0 is special. Index 0 has no predecessor — there's no node whose next we can edit. Instead the new node becomes the head: point its next at the old head and return it. This is exactly why the function returns a head at all: only here does the head change, and the caller has to learn about it.
The two-line splice, and why order matters. Standing on prev, we do newNode.next = prev.next first, then prev.next = newNode. The first line saves the rest of the list onto the new node; the second hooks the new node into place. Flip them and prev.next = newNode overwrites the only reference to the tail before you've copied it — prev.next now points at newNode, and newNode.next = prev.next just points the new node back at itself. The tail is gone. Set the new node's next before you touch the predecessor's next.
Why the loop is counted, not condition-driven. We aren't walking to the end of the list; we're walking to a fixed index. A for loop that runs position − 1 times lands precisely on the predecessor. A while (cur.next != null) loop would overshoot to the tail.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
list = [1, 2, 3], data = 9, position = 1Array state
start
prev on head (index 0)
[1, 9, 2, 3]C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The named trap here is losing the next pointer. The instant you overwrite prev.next you've discarded your only link to everything downstream — so you stash it on newNode.next first. That 'save the next pointer before you rewire' reflex is the single most reused move across reverse, rotate, and reorder.
ComplexityO(n) time, O(1) space — We take at most position − 1 ≤ n − 1 steps to reach the predecessor, then do O(1) pointer work. No extra structures, so O(1) space.
E · Edge cases and pitfalls7list = [], data = 5, position = 0 — Empty list, head insert: newNode.next = null, return newNode → [5].Explore edge casesHide edge cases
Edge cases handled
list = [], data = 5, position = 0Empty list, head insert: newNode.next = null, return newNode → [5].list = [1, 2, 3], data = 9, position = 3position == length: walk to last node (index 2), prev.next is null, splice 9 at the tail → [1, 2, 3, 9].list = [7], data = 4, position = 1Single node, append: prev stays on node 7, newNode.next = null, prev.next = newNode → [7, 4].
Pitfalls
- Walking position steps instead of position − 1 — you overshoot and insert one slot too late.
- Writing prev.next = newNode before newNode.next = prev.next — orphans the entire tail.
- Forgetting the position == 0 branch — a null predecessor causes a crash or a dropped head.
- Not returning the head — the caller silently keeps the old head and loses a head insert.
Approach 2 of 2
Recursive — Decrement Position Down the List
1Hint 1Explore hintHide hint
If inserting at position p in the whole list, what is the equivalent problem on head.next?
2Hint 2Explore hintHide hint
Each step that doesn't insert moves one node forward and reduces the target position by one.
3Hint 3Explore hintHide hint
The base case is position == 0: build the new node, point it at the current head, and return it as the new sub-head.
A · Core idea
We express insertion as: insert at position p in head equals attach head in front of (insert at position p − 1 in head.next).
The base case carries the splice. When position == 0, the new node belongs right here: set newNode.next = head and return newNode. Every caller above takes that returned sub-head and reattaches it as its own next, so the splice ripples back up the chain automatically.
The recursive step rebuilds the prefix. For position > 0, the current head stays where it is; we recurse on head.next with position − 1 and assign the result to head.next. Reassigning head.next is what stitches the (possibly new) sub-head back in — it's the same 'attach the merge of the rest' shape used in list recursion generally.
Why the iterative version is the safer lead. This reads cleanly and needs no explicit predecessor handling, but each node walked adds a stack frame. With n up to 1000 that's fine here, yet on long lists the iterative O(1)-space walk avoids any stack-overflow risk. Same O(n) time, more space — so present iterative first and offer this as the elegant variant.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
list = [1, 2, 3], data = 9, position = 2Interactive diagram
How the recursion unwinds
insert([1,2,3], 2)Calls peel nodes until position hits 0; the splice happens at the base and reattaches as calls return.
[1, 2, 9, 3]C · Code with teaching comments
Reference implementation previewpublic ListNode insertNodeAtPosition(ListNode head, int data, int position) { if (position == 0) { ListNode newNode = new ListNode(data); newNode.next = head; return newNode;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Recursion hides the predecessor bookkeeping inside the call stack: 'reassign head.next to the recursive result' is the splice, performed implicitly as calls unwind. It's the same move as recursive merge — attach the current head in front of the solved remainder.
ComplexityO(n) time, O(n) space — One recursive call per node walked, up to position ≤ n calls, each O(1) → O(n) time. The recursion depth equals position, so O(n) stack space in the worst case.
E · Edge cases and pitfalls3Missing the position == 0 base case — infinite recursion or a null dereference on head.next.Explore edge casesHide edge cases
Pitfalls
- Missing the position == 0 base case — infinite recursion or a null dereference on head.next.
- Forgetting to reassign head.next to the recursive result — the splice never connects.
- Using recursion on very long lists where the iterative O(1)-space walk is safer.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Rewiring in the wrong order (losing the next pointer)
Setting prev.next = newNode first overwrites the only reference to the rest of the list. The follow-up newNode.next = prev.next then points the new node at itself, and every downstream node is orphaned.
Explore the code comparisonHide the code comparison
Rewiring in the wrong order (losing the next pointer)
Setting prev.next = newNode first overwrites the only reference to the rest of the list. The follow-up newNode.next = prev.next then points the new node at itself, and every downstream node is orphaned.
Don't write this
prev.next = newNode;
newNode.next = prev.next; // prev.next is now newNode — points to itself!Write this instead
newNode.next = prev.next; // save the tail first
prev.next = newNode; // then hook in2Off-by-one on the walk
Inserting at index k requires standing on index k − 1. Walking k steps lands on index k, so the new node ends up one slot too late.
Explore the code comparisonHide the code comparison
Off-by-one on the walk
Inserting at index k requires standing on index k − 1. Walking k steps lands on index k, so the new node ends up one slot too late.
Don't write this
prev = head
for _ in range(position): # one step too many
prev = prev.nextWrite this instead
prev = head
for _ in range(position - 1):
prev = prev.next3Ignoring the head-insert case
Position 0 has no predecessor. Walking position − 1 = −1 steps either skips the loop and leaves prev on the head (inserting at index 1, wrong) or dereferences null. Branch on it explicitly and return the new head.
Explore the code comparisonHide the code comparison
Ignoring the head-insert case
Position 0 has no predecessor. Walking position − 1 = −1 steps either skips the loop and leaves prev on the head (inserting at index 1, wrong) or dereferences null. Branch on it explicitly and return the new head.
Don't write this
prev = head
for _ in range(position - 1):
prev = prev.next # crashes or misbehaves when position == 0Write this instead
if position == 0:
new_node.next = head
return new_nodeRevise
Carry the pattern into the interview
Pattern to remember
Walk to predecessor, then splice (set new.next before rewiring prev.next)
Code pattern to memorize
if position == 0: newNode.next = head; return newNode
prev = head
repeat position - 1 times: prev = prev.next
newNode.next = prev.next
prev.next = newNode
return headRules to remember
- 1To insert at index
k, stop on the node at indexk − 1— walkposition − 1steps, notposition. - 2Set
newNode.next = prev.nextbeforeprev.next = newNode. Reverse the order and you lose the rest of the list. - 3Position
0has no predecessor — insert at the head and return the new head, don't try to walk. - 4The head can change, so the function must return the (possibly new) head, never assume the caller keeps the old one.
- 5Use a counter loop, not a
while (cur.next != null)loop — you're stopping at a fixed index, not the end.
Use this pattern when
- Insert into a singly linked list at a known 0-based index
- Building or editing a list where order matters and you have the target slot
- Any 'splice one node between two existing nodes' subproblem
- Warm-up for harder relink problems (reverse a sublist, rotate, reorder)
Choose another pattern when
- You always insert at the front → that's O(1) insert-at-head, no walk needed
- You always insert at the back and keep a tail pointer → O(1) append, no walk
- Random access by index is needed repeatedly → an array or dynamic array beats a linked list
- The structure is a doubly linked list with a known node reference → splice in O(1) using prev/next directly
Interview takeaway
Every linked-list insertion is the same two-line splice — the only question is how you reach the predecessor. Get the walk-to-position-minus-one and the set-next-before-rewire ordering right and rotate, reorder, and reverse-sublist all become routine.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternWalk-to-predecessor then two-line splice — the atomic move behind every linked-list edit. The same skeleton (reach a node, save its next, rewire) powers delete-at-position, reverse-a-sublist, rotate-list, and reorder-list.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Insert at HeadThe position == 0 case in isolation — O(1), no walk, just point the new node at the head and return it.
- Delete a Node at a PositionSame walk-to-predecessor, but relink prev.next = prev.next.next instead of splicing in.
- Remove Nth Node From End of ListReach a position relative to the tail with a two-pointer gap, then do the same predecessor relink.