Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Insertion at a Given Position in a Linked List

EASYProblemSolveExternal Links

Description

You are given the head of a singly linked list, a position pos (1-based index), and a value val. Your task is to insert a new node containing val at the given position in the linked list and return the head of the modified list.

If pos is 1, the new node becomes the new head. If pos equals the size of the list plus one, the new node is appended at the end. For any position in between, the new node is spliced into the chain at that exact spot, with the existing nodes shifting one position forward.

This is a fundamental linked list operation that tests your understanding of pointer manipulation — specifically, how to traverse to the right location and rewire two pointers without breaking the chain or losing references to the rest of the list.

Examples

Example 1

Input: Linked List: 1 → 3, pos = 3, val = 4

Output: 1 → 3 → 4

Explanation: The position 3 is one past the current end of the list (which has 2 nodes). So we insert value 4 at the end. The modified list becomes 1 → 3 → 4.

Example 2

Input: Linked List: 1 → 2 → 9, pos = 2, val = 5

Output: 1 → 5 → 2 → 9

Explanation: We need to insert value 5 at position 2 (1-based). The node currently at position 2 is the one with data 2. After insertion, the new node (5) takes position 2, and the old node (2) shifts to position 3. The modified list is 1 → 5 → 2 → 9.

Example 3

Input: Linked List: 4 → 7 → 12 → 8, pos = 1, val = 2

Output: 2 → 4 → 7 → 12 → 8

Explanation: Position 1 means we are inserting at the very beginning of the list. The new node with value 2 becomes the new head, and the old head (4) becomes the second node. No traversal is needed — this is an O(1) operation.

Constraints

  • 1 ≤ List Size ≤ 10⁴
  • 1 ≤ pos ≤ List Size + 1
  • 1 ≤ val ≤ 10⁴
  • The position is guaranteed to be valid (within bounds of the list plus one for end insertion).
  • The linked list is singly linked — each node has a data field and a next pointer.

Editorial

Brute Force Approach - Convert to Array, Insert, Rebuild

Intuition

If you are not yet comfortable with pointer manipulation, a straightforward way to solve this problem is to avoid working with pointers altogether. Instead, convert the linked list into an array, use the array's built-in insertion capability to place the new value at the correct position, and then rebuild a fresh linked list from the modified array.

This approach is conceptually simple:

  1. Walk through the linked list and collect all values into an array.
  2. Insert the new value at position pos - 1 in the array (converting from 1-based to 0-based indexing).
  3. Build a new linked list from the array.

While this works, it wastes memory by creating an entirely new data structure (the array) and then creating entirely new nodes. It defeats the purpose of using a linked list in the first place, since the main advantage of linked lists is that insertions can be done in-place by adjusting pointers. However, as a beginner's first attempt, it is a valid starting point to understand the problem before optimizing.

Step-by-Step Explanation

Let's trace this approach on: Linked List: 1 → 2 → 9, pos = 2, val = 5.

Step 1: Traverse the linked list and collect all values into an array.

  • Visit node(1), add 1 to array. Array: [1]
  • Visit node(2), add 2 to array. Array: [1, 2]
  • Visit node(9), add 9 to array. Array: [1, 2, 9]

Step 2: Insert value 5 at array index pos - 1 = 1.

  • Array before: [1, 2, 9]
  • Shift elements at index 1 and beyond one position to the right.
  • Place 5 at index 1.
  • Array after: [1, 5, 2, 9]

Step 3: Build a new linked list from the modified array.

  • Create node(1) as head.
  • Create node(5), link to head.
  • Create node(2), link to node(5).
  • Create node(9), link to node(2).
  • Result: 1 → 5 → 2 → 9

Step 4: Return the head of the new linked list.

Brute Force — Convert to Array, Insert, and Rebuild — Watch how we extract all values from the linked list into an array, insert the new value, and build a brand-new linked list from the modified array.

Algorithm

  1. Initialize an empty array values.
  2. Traverse the linked list from head to end, appending each node's data to values.
  3. Insert val at index pos - 1 in the array (converting 1-based position to 0-based index).
  4. Build a new linked list by iterating through the modified array and creating nodes.
  5. Return the head of the new linked list.

Code

#include <vector>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

Node* insertAtPosition(Node* head, int pos, int val) {
    // Step 1: Extract values into an array
    vector<int> values;
    Node* current = head;
    while (current != nullptr) {
        values.push_back(current->data);
        current = current->next;
    }

    // Step 2: Insert value at the correct position (1-based to 0-based)
    values.insert(values.begin() + (pos - 1), val);

    // Step 3: Rebuild linked list from the array
    Node* newHead = new Node(values[0]);
    Node* tail = newHead;
    for (int i = 1; i < values.size(); i++) {
        tail->next = new Node(values[i]);
        tail = tail->next;
    }

    return newHead;
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insertAtPosition(head, pos, val):
    # Step 1: Extract values into a list
    values = []
    current = head
    while current is not None:
        values.append(current.data)
        current = current.next

    # Step 2: Insert value at the correct position (1-based to 0-based)
    values.insert(pos - 1, val)

    # Step 3: Rebuild linked list from the list
    new_head = Node(values[0])
    tail = new_head
    for i in range(1, len(values)):
        tail.next = Node(values[i])
        tail = tail.next

    return new_head
import java.util.ArrayList;
import java.util.List;

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Solution {
    public Node insertAtPosition(Node head, int pos, int val) {
        // Step 1: Extract values into an array
        List<Integer> values = new ArrayList<>();
        Node current = head;
        while (current != null) {
            values.add(current.data);
            current = current.next;
        }

        // Step 2: Insert value at the correct position (1-based to 0-based)
        values.add(pos - 1, val);

        // Step 3: Rebuild linked list from the array
        Node newHead = new Node(values.get(0));
        Node tail = newHead;
        for (int i = 1; i < values.size(); i++) {
            tail.next = new Node(values.get(i));
            tail = tail.next;
        }

        return newHead;
    }
}

Complexity Analysis

Time Complexity: O(n)

Traversing the linked list to build the array takes O(n). Inserting into the array at position pos requires shifting elements, which is O(n) in the worst case. Rebuilding the linked list takes O(n). Overall: O(n).

Space Complexity: O(n)

We create an array of size n to store the values, and then create n+1 new nodes for the rebuilt list. Total extra space: O(n).

Why This Approach Is Not Efficient

The brute force approach works but has a glaring inefficiency: it uses O(n) extra space for the array and creates entirely new nodes, wasting memory. The entire point of a linked list is that insertions can be performed in-place by rewiring a couple of pointers — no copying, no shifting, no rebuilding.

Additionally, the array insertion step itself requires shifting elements (O(n) work), which is the exact problem linked lists are designed to avoid. Converting to an array and back is like building a house, demolishing it, and rebuilding it from scratch just to add one room — when you could have simply attached the new room to the existing structure.

The optimal approach eliminates all of this overhead: traverse the linked list to the node just before the insertion point, create one new node, and adjust two pointers. No extra data structures, no rebuilding, no wasted memory.

Comparison chart showing Brute Force (O(n) space, copies all data, rebuilds entire list) versus Optimal (O(1) space, modifies in-place, adjusts two pointers)
Comparison chart showing Brute Force (O(n) space, copies all data, rebuilds entire list) versus Optimal (O(1) space, modifies in-place, adjusts two pointers)

Optimal Approach - In-Place Pointer Manipulation

Intuition

The optimal approach works directly with the linked list's pointers — no extra data structures, no copying, no rebuilding.

The key insight is that to insert a node at position pos, you need a reference to the node at position pos - 1 (the node just before the insertion point). Once you have that reference, the insertion itself is just two pointer assignments:

  1. new_node.next = prev.next — The new node now points to whatever was at position pos before.
  2. prev.next = new_node — The node at position pos - 1 now points to the new node.

These two steps splice the new node into the chain without disturbing any other nodes.

There is one special case: when pos == 1, there is no "previous node." In this case, the new node becomes the new head. We set new_node.next = head and return new_node as the new head.

The traversal to find the previous node takes O(pos) time in the worst case (O(n) if inserting at the end), but the actual insertion is always O(1). And crucially, we use only O(1) extra space — just the one new node.

Step-by-Step Explanation

Let's trace inserting val = 5 at pos = 2 in the list: 1 → 2 → 9.

Step 1: Check if pos == 1. It is not (pos = 2), so this is not a head insertion.

Step 2: Create a new node with data = 5. Its next pointer is null initially.

Step 3: We need to find the node at position pos - 1 = 1. Start at head (position 1). We need to traverse 0 more nodes — current is already at position 1. So prev = head (node with data 1).

Step 4: Set new_node.next = prev.next. The new node (5) now points to the node that was at position 2 (node with data 2). Chain so far: ... → 5 → 2 → 9.

Step 5: Set prev.next = new_node. Node(1).next now points to node(5) instead of node(2). The chain is complete: 1 → 5 → 2 → 9.

Step 6: Return head. The list is now 1 → 5 → 2 → 9. We inserted the value using only two pointer updates and one new node — no arrays, no rebuilding.

Notice the order of Steps 4 and 5 matters. If we did Step 5 first (set prev.next = new_node), we would lose the reference to node(2) before linking the new node to it.

Optimal — In-Place Insertion at Position 2 — Watch how we traverse to the predecessor node and splice the new node into the linked list using just two pointer adjustments, without any extra data structures.

Algorithm

  1. Create a new node with the given value val.
  2. Special case — Insert at head (pos == 1):
    a. Set new_node.next = head.
    b. Return new_node as the new head.
  3. General case — Insert at position pos:
    a. Set current = head.
    b. Traverse pos - 2 steps forward to reach the node at position pos - 1. (We traverse pos - 2 times because we start at position 1, and we need to reach position pos - 1).
    c. Set new_node.next = current.next (link new node to the successor).
    d. Set current.next = new_node (link predecessor to new node).
  4. Return head (unchanged since we did not modify the head).

Code

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

Node* insertAtPosition(Node* head, int pos, int val) {
    Node* newNode = new Node(val);

    // Special case: insert at the beginning
    if (pos == 1) {
        newNode->next = head;
        return newNode;
    }

    // Traverse to the node at position (pos - 1)
    Node* current = head;
    for (int i = 1; i < pos - 1 && current != nullptr; i++) {
        current = current->next;
    }

    // Insert the new node after current
    if (current != nullptr) {
        newNode->next = current->next;
        current->next = newNode;
    }

    return head;
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insertAtPosition(head, pos, val):
    new_node = Node(val)

    # Special case: insert at the beginning
    if pos == 1:
        new_node.next = head
        return new_node

    # Traverse to the node at position (pos - 1)
    current = head
    for _ in range(1, pos - 1):
        if current is None:
            return head
        current = current.next

    # Insert the new node after current
    if current is not None:
        new_node.next = current.next
        current.next = new_node

    return head
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Solution {
    public Node insertAtPosition(Node head, int pos, int val) {
        Node newNode = new Node(val);

        // Special case: insert at the beginning
        if (pos == 1) {
            newNode.next = head;
            return newNode;
        }

        // Traverse to the node at position (pos - 1)
        Node current = head;
        for (int i = 1; i < pos - 1 && current != null; i++) {
            current = current.next;
        }

        // Insert the new node after current
        if (current != null) {
            newNode.next = current.next;
            current.next = newNode;
        }

        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, we insert at the last position, requiring a traversal of all n nodes. When inserting at the head (pos = 1), the time is O(1) since no traversal is needed. On average, we traverse about n/2 nodes, but the worst case is O(n).

Space Complexity: O(1)

We create exactly one new node and use a single pointer variable for traversal. No arrays, no extra data structures — the insertion is done entirely in-place by manipulating existing pointers.