Insert a Node at a Given Position in a Linked List

Medium10–15 min

Topics

Linked ListTraversal

Companies

AmazonMicrosoftAdobeFlipkart

Given the head of a singly linked list, an integer val, and a 0-indexed position, insert a new node holding val so that it ends up at index position in the resulting list, and return the head. position = 0 is exactly the insert-at-the-beginning case, and position equal to the list's current length is exactly the insert-at-the-end case — this problem generalizes both. The optimal solution walks to the node just before the target index and redirects two pointers, without touching any other existing node.

Test Case 1:

Input:head = [1, 2, 4], val = 3, position = 2

Output:[1, 2, 3, 4]

Explanation:Index 2 (0-indexed) is between the existing 2 and 4 — the new node lands right there.

Test Case 2:

Input:head = [5, 10, 15], val = 1, position = 0

Output:[1, 5, 10, 15]

Explanation:position 0 makes this equivalent to inserting at the beginning.

Test Case 3:

Input:head = [7, 8], val = 9, position = 2

Output:[7, 8, 9]

Explanation:position equal to the list's length makes this equivalent to inserting at the end.

Constraints

◆0 ≤ number of nodes in head ≤ 10⁴
◆-10⁹ ≤ node value, val ≤ 10⁹
◆0 ≤ position ≤ length of head — position is 0-indexed, so position 0 means the new head and position length means the new tail

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

head (list values) — 0-6 integersvalposition (0-indexed)

1	class Solution {
2	public Node insertAtPosition(Node head, int val, int position) {
3	Node newNode = new Node(val);
4	if (position == 0) {
5	newNode.next = head;
6	return newNode;
7	}
8	Node curr = head;
9	for (int i = 0; i < position - 1; i++) {
10	curr = curr.next;
11	}
12	newNode.next = curr.next;
13	curr.next = newNode;
14	return head;
15	}
16	}
17

null

Variables

newNode3

INITIALIZE

Create a new node holding 3. It isn't linked into the list yet.

Step 1 / 7

Approach & Solutions

Brute Force — Copy to Array, Splice, Rebuild List

Brute

Walk the existing list into a plain array, then splice val into that array at the given position, shifting every later element over by one. Throw the entire original list away and build a brand-new list from the array using a dummy + tail pointer. Correct, but every existing node is read and re-allocated even though only one new node actually needed to be spliced in.

TimeO(n)

SpaceO(n)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node insertAtPosition(Node head, int val, int position) {
        List<Integer> vals = new ArrayList<>();
        Node curr = head;
        while (curr != null) {
            vals.add(curr.val);
            curr = curr.next;
        }
        vals.add(position, val);
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : vals) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Optimal — Traverse to Position-1, Splice In

Optimal

Position 0 is really just insert-at-the-beginning — handle it the same O(1) way. Otherwise, walk from head to the node just before the target position, then redirect two pointers: the new node's next takes over what curr used to point at, and curr's next is redirected through the new node. No existing node is copied or re-allocated.