Insert a Node in a Doubly Linked List

Easy10–15 min

Topics

Linked ListDoubly Linked ListTraversal

Companies

AmazonMicrosoftAdobe

Given the head of a doubly linked list, a value, and a 0-indexed position, insert a new node holding that value at that position and return the new head. Position 0 means the new node becomes the head; a position equal to the list's current length means it becomes the new tail. Splicing a node into the middle only ever touches the handful of pointers right around the insertion point — everything else in the list stays exactly as it was. In a singly linked list that means redirecting two next pointers; in a doubly linked list, the matching prev pointers on both sides of the new node get redirected the same way, so the list can still be walked backward through the new node just as easily as forward.

Test Case 1:

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

Output:[2, 5, 6, 7, 9]

Explanation:Position 2 (0-indexed) sits between the existing 5 and 7 — the new node is spliced in right there, with both its neighbors' links updated.

Test Case 2:

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

Output:[0, 1, 2, 3]

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

Test Case 3:

Input:head = [], val = 5, position = 0

Output:[5]

Explanation:Inserting into an empty list at position 0 just creates the first node.

Constraints

◆0 ≤ number of nodes in head ≤ 200
◆-1000 ≤ node value, val ≤ 1000
◆0 ≤ position ≤ length of head — position is 0-indexed, so position 0 means the new head and position length means the new tail
◆This platform's judge reads back only the forward (next) traversal — a real doubly linked implementation also relinks .prev in both directions around the new node

🚀

Try the Dry Run

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

Approach & Solutions

Brute Force — Copy to Array, Splice, Rebuild

Brute

Copy every value into an array, splice the new value into that array at the target position, then rebuild the list from scratch. Correct, but it discards and reallocates every node instead of relinking the handful of pointers that actually needed to change.

TimeO(n)

SpaceO(n)

Java

Try it out

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

class Solution {
    public Node insertDLL(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. In a true doubly linked list, the new node's prev is also pointed back at curr, and curr's old successor has its prev pointed at the new node — the same splice, mirrored in the other direction.