☕ DSA Java Articles

Topics › Linked List › Learn 1D LinkedList

Insertion at the head of Linked List

Easy TUF ID 356 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list and an integer val. Create a new node holding val, place it in front of the current first node, and return the head of the resulting list. The list may be empty, in which case the new node is the entire list.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer. The operation must not visit the rest of the list.

Example 1

list = 2 -> 3 -> 4, val = 1
answer = 1 -> 2 -> 3 -> 4      // the new node becomes the head

Example 2

list = (empty), val = 5
answer = 5                     // the new node is both head and tail

Example 3

list = 9, val = 9
answer = 9 -> 9                // equal values are still two distinct nodes

The node type is the usual one: an int val and a ListNode next reference, with next == null marking the end of the list, and a null head meaning the empty list.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Intuition. A linked list is nothing more than a reference to its first node. To put a new node in front, we need exactly two things to be true afterwards: the new node’s next points at the old first node, and whoever holds the list now holds a reference to the new node. The first is one assignment; the second is achieved by returning the new node so the caller can store it as the head. Nothing else in the list changes, which is why the operation is constant time regardless of how long the list is.

Algorithm.

  1. Create node = new ListNode(val).
  2. Set node.next = head. If head is null, this sets next to null, which is exactly right for a one-node list.
  3. Return node; it is the new head.
static ListNode insertAtHead(ListNode head, int val) {
    ListNode node = new ListNode(val);
    node.next = head;                // also correct when head is null: the new node is then the only node
    return node;
}

Complexity. Time O(1): one allocation and one assignment, independent of n. Space O(1) beyond the new node itself.

Dry run on 2 -> 3 -> 4 with val = 1:

step node node.next returned head
create [1] null -
link [1] the node [2] -
return - - [1] -> 2 -> 3 -> 4

The important detail is that the caller must use the returned value: head = insertAtHead(head, 1);. Java passes references by value, so the method cannot change the caller’s head variable itself; it can only hand back the new one. Forgetting to assign the result is the most common bug with this operation, and the list silently stays unchanged.

Approach 2: The same operation as one expression

Intuition. The two-argument constructor already does “create a node whose next is this reference”. Insertion at the head is therefore a single expression, which is how you will usually see it written in solutions once the idea is familiar.

Algorithm.

  1. Return new ListNode(val, head).
static ListNode insertAtHeadOneLiner(ListNode head, int val) {
    return new ListNode(val, head);
}

Complexity. Time O(1), space O(1). It is identical in behaviour to Approach 1; the test harness runs both against the same expected output on every input.

Repeating this operation is a useful mental model: inserting 1, 2, 3, 4, 5 one after another at the head produces 5 -> 4 -> 3 -> 2 -> 1. The most recently inserted element is always first, which is exactly the behaviour of a stack. A stack backed by a linked list is just insert-at-head for push and delete-at-head for pop.

Why the head and not the tail

Intuition. It is worth contrasting the head operation with insertion at the tail to see why linked lists are “cheap at the front”. To append we need a reference to the last node, and a singly linked list gives us no way to reach it except by walking from the head.

Algorithm.

  1. Create the new node. If the list is empty, it is the new head; return it.
  2. Walk temp from the head until temp.next == null, which is the last node.
  3. Set temp.next = node and return the unchanged head.
static ListNode insertAtTail(ListNode head, int val) {
    ListNode node = new ListNode(val);
    if (head == null) return node;
    ListNode temp = head;
    while (temp.next != null) temp = temp.next;
    temp.next = node;
    return head;
}

Complexity. Time O(n) for the walk, space O(1). Queue implementations avoid the walk by keeping an extra tail reference that is updated on every append, which restores O(1) at the cost of one more field to keep consistent.

Note the loop condition temp.next != null rather than temp != null. We want to stop on the last node, not fall off the end, because we have to modify that node’s next. This “stop one before” pattern recurs in every insertion and deletion that touches the middle of a list.

Generalisation: insert at position k

Intuition. Insertion at the head is the k = 1 case of inserting before the k-th node (1-based). For any other k, the new node must go between node k - 1 and node k, so we walk to node k - 1, point the new node at its successor, and point it at the new node. The head case is special only because there is no node k - 1 to attach to, which is why it is handled before the loop.

Algorithm.

  1. If k < 1, the position does not exist; return the list unchanged.
  2. If k == 1, return new ListNode(val, head) (Approach 2).
  3. Walk temp from the head for k - 2 steps so it stops on node k - 1. If it becomes null first, the list has fewer than k - 1 nodes and the position does not exist; return the head unchanged.
  4. Set temp.next = new ListNode(val, temp.next) and return the head.
static ListNode insertAtPosition(ListNode head, int k, int val) {
    if (k < 1) return head;                                               // no such position: leave the list alone
    if (k == 1) return new ListNode(val, head);
    ListNode temp = head;
    for (int i = 1; i < k - 1 && temp != null; i++) temp = temp.next;    // stop on node k - 1
    if (temp == null) return head;                                        // fewer than k - 1 nodes: position does not exist
    temp.next = new ListNode(val, temp.next);
    return head;
}

Complexity. Time O(k), which is O(1) for the head and O(n) for k = n + 1 (appending). Space O(1).

The loop runs with i from 1 to k - 2, so temp moves k - 2 times and lands on the (k - 1)-th node. With k = n + 1 it lands on the last node and the insertion appends, which the tests confirm by comparing against insertAtTail. With k = n + 2 it falls off the end and the list is returned unchanged.

Edge cases and pitfalls