Insert a Node at the Beginning of a Linked List
Solve this Problem
Given the
head of a singly linked list and an integer val, insert a new node holding val at the very front of the list, and return the head of the resulting list.
Because a linked list is only reachable by following next pointers from its head, inserting at the front never has to touch or shift any existing node — it just needs to change what counts as the head. The optimal solution does this in O(1)O(1) — Constant TimeThe operation takes the same, small number of steps no matter how long the list is — unlike inserting at the front of an array, which must shift every existing element over., regardless of how long the list is.
Test Case 1:
Input:head = [2, 3, 4], val = 1
Output:[1, 2, 3, 4]
Explanation:The new node holding 1 becomes the new head, followed by the untouched original list.
Test Case 2:
Input:head = [], val = 5
Output:[5]
Explanation:Inserting into an empty list makes the new node the only node.
Test Case 3:
Input:head = [7], val = 9
Output:[9, 7]
Explanation:The new node goes in front of the single existing node.
Constraints
- ◆
0 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value, val ≤ 10⁹ - ◆
Do not copy or rebuild the existing nodes for the optimal solution
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public Node insertAtBeginning(Node head, int val) { |
| 3 | Node newNode = new Node(val); |
| 4 | newNode.next = head; |
| 5 | return newNode; |
| 6 | } |
| 7 | } |
| 8 |
1
Variables
newNode
1INITIALIZE
Create a new node holding 1. Its next is null for now.
Step 1 / 3
Approach & Solutions
Brute Force — Copy to Array, Prepend, Rebuild List
BruteWalk the existing list into a plain array, with val placed first. Then throw the entire original list away and build a brand-new list from that array using a dummy + tail pointer. Correct, but it reads and re-allocates every existing node just to move them one position over — work that a single pointer update could avoid entirely.
Time
O(n)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node insertAtBeginning(Node head, int val) {
9 List<Integer> vals = new ArrayList<>();
10 vals.add(val);
11 Node curr = head;
12 while (curr != null) {
13 vals.add(curr.val);
14 curr = curr.next;
15 }
16 Node dummy = new Node(0);
17 Node tail = dummy;
18 for (int v : vals) {
19 tail.next = new Node(v);
20 tail = tail.next;
21 }
22 return dummy.next;
23 }
24}Optimal — New Node Points to Old Head
OptimalA new node's next pointer only needs to point at the current head — that single connection already makes the new node the front of the list. No existing node is read, copied, or modified.
Time
O(1)Space
O(1)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node insertAtBeginning(Node head, int val) {
9 Node newNode = new Node(val);
10 newNode.next = head;
11 return newNode;
12 }
13}