Insertion at a Given Position in a Linked List

You are given the head of a singly linked list, a 1-based position pos, and a value val. Insert a new node holding val at position pos and return the head of the modified list.

After the insertion, the new node occupies the pos-th slot (counting from 1). Everything that was at position pos and beyond simply slides one step to the right; everything before it stays exactly where it was.

Two boundaries are worth naming:

pos = 1 means the new value becomes the new head.
pos = size + 1 means the new value is appended just past the current last node.

Hints

· Stuck? Reveal one nudge at a time.

You never touch the node at position pos directly — which node do you actually need a handle on?

Inserting at position 1 has no predecessor inside the list. Is there a way to give it one?

Put a dummy node before head, walk pos-1 steps, then set new.next = prev.next and prev.next = new.

Common doubts

1-based. Position 1 means the new node becomes the head; position size + 1 appends at the end.

Position 1 has no predecessor inside the list. A dummy node before head gives it one, so a single loop handles every position with no special case.

Yes. Set new.next = prev.next first, then prev.next = new. Reversing them makes the new node point at itself and loses the rest of the list.

Interview follow-ups

· What an interviewer asks next.

Same walk to the predecessor, then a single rewire: prev.next = prev.next.next — after guarding that prev.next exists.

You would also fix the new node's prev pointer and the successor's prev pointer — four links instead of two, but still O(1) at the spot.

Fun facts

The dummy (sentinel) node trick shows up in almost every list-mutation problem — insert, delete, merge, partition — because it makes the head stop being a special case.
Inserting mid-list is where linked lists beat arrays: no O(n) shifting of later elements, just two pointer writes once you're at the spot.

Asked at

AmazonMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: head = [1, 3], pos = 3, val = 4
Output: 1 -> 3 -> 4
Position 3 is one past the last node, so 4 is appended to the end.

Example 2

Input: head = [1, 2, 9], pos = 2, val = 5
Output: 1 -> 5 -> 2 -> 9
5 is inserted before the node at position 2, landing between 1 and 2.

Constraints

- 1 <= list size <= 10^4 - 1 <= pos <= list size + 1 - 1 <= val <= 10^4

Inserting at an arbitrary position is where linked lists start to feel powerful: no shifting a million elements like an array would. You reach the one spot that matters, rewire two pointers, and you're done — the rest of the list never moves.

Prerequisites

Before you start

· Concepts used directly in the solution.

Singly linked list. A chain of nodes where each node stores a value and a next pointer to the following node; the last node's next is null.

Pointer rewiring. Insertion is two assignments — point the new node at what comes next, then point the predecessor at the new node.

Dummy (sentinel) node. A throwaway node placed before head so that inserting at position 1 needs no special case.

Understand the problem

In plain terms: find the node at position pos - 1 (the predecessor), make the new node point to whatever the predecessor pointed to, then make the predecessor point to the new node.

Worked example — head = [1, 3], pos = 3, val = 4

before:  head → [1] → [3] → null        pos = 3, val = 4
walk to the node before position 3 → that's [3] (the 2nd node)
create:  new [4], set [4].next = [3].next   (null)
relink:  [3].next = [4]
after:   head → [1] → [3] → [4] → null
answer:  1 -> 3 -> 4

Clarifying questions

Naming the boundaries out loud — position 1, position size+1 — before touching a pointer is exactly what an interviewer wants to hear.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is pos 1-based or 0-based?”

It changes every index in your loop; here it is 1-based, so position 1 is the head.

Edge cases

“Can pos be 1, and can it be size + 1?”

Yes to both — position 1 replaces the head, and size+1 appends at the very end; a good solution handles both without extra branches.

Constraints and scale

“How large can the list get?”

Up to 10^4 nodes, so a single walk to the position is fine, but copying the whole list into an array is needless extra memory.

The ideal opening — say it like this

Let me confirm a couple of things before I code.

Position is 1-based, so pos equal to 1 means the new node becomes the head — correct?

And pos equal to size plus one means I append at the end, which I'll cover with a sentinel node so there's no special case.

Key observations

1Aha

You only ever touch the predecessor

Insertion happens after the node at position pos - 1. That predecessor is the only node you need a handle on — everything downstream is reached through its next pointer.

prev = node at position pos-1
new.next  = prev.next     # new points at the rest
prev.next = new           # prev points at new

2Aha

A dummy node erases the head special case

Position 1 has no predecessor inside the list — the predecessor is the head slot. Place a sentinel dummy before head; now position 1's predecessor is dummy, and one loop handles every position uniformly. Return dummy.next at the end.

3Aha

Order of the two links is not optional

Set new.next = prev.next before prev.next = new. Reverse them and prev.next already points at new, so new.next = prev.next makes the node point at itself and the tail is lost.

Brute force vs optimal

	Copy to array	One-pass splice
Idea	Dump values into an array, insert, rebuild the list	Walk to pos-1, rewire two pointers
Time	O(n)	O(n)
Space	O(n)	O(1)
Passes	Two (copy + rebuild)	One (partial walk)

Both are linear in time, but the array copy duplicates data that already lives in memory. The optimal move reaches the spot once and rewires in place — full code is in the Approaches selector below.

Summary

Key takeaway

To insert at position pos, walk a sentinel-anchored pointer pos - 1 steps to reach the predecessor, then splice: new.next = prev.next, prev.next = new. The dummy node makes position 1 ordinary, and the two-line rewire keeps it O(1) extra space.

dummy = Node(0); dummy.next = head
prev = dummy
repeat pos-1 times (or until prev.next is null): prev = prev.next
prev.next = Node(val, prev.next)
return dummy.next