Given the head of a singly linked list and an integer value, insert a new node at the beginning of the linked list and return the new head.
Example 1
Input: head = [2, 5, 8, 7], value = 10
Output: [10, 2, 5, 8, 7]
Explanation: Value 10 gets inserted before the current head, so the original chain starts after the new node.
Example 2
Input: head = [], value = 4
Output: [4]
Explanation: Empty linked list insertion creates a new single-node linked list.
Approach
Head insertion in a singly linked list is one of the easiest pointer updates because no traversal is needed. The current head already marks the correct attachment point, so the only job is to create a new node and connect the new node to the old head.
Algorithm
Create a new node with the given value.
Attach the next pointer of the new node to the current head.
Return the new node as the updated head.
Dry Run
insert new head
Solution
#include <bits/stdc++.h>using namespace std;struct Node { int data; Node* next; Node(int value) { data = value; next = nullptr; }};class Solution {public: // Function to insert a new node at the head of the linked list. Node* insertNewHead(Node* head, int value) { // Create a new node for the inserted value. Node* newHead = new Node(value); // Attach the current head after the new node. newHead->next = head; // Return the new node as the updated head. return newHead; }};// Function to create a linked list from an array.Node* createList(vector<int>& values) { // Return null for an empty input array. if (values.empty()) { return nullptr; } // Create the head node from the first value. Node* head = new Node(values[0]); Node* tail = head; // Append remaining values one by one. for (int index = 1; index < (int)values.size(); index++) { tail->next = new Node(values[index]); tail = tail->next; } return head;}// Function to print linked list values.void printList(Node* head) { // Start traversal from the head node. Node* current = head; // Print every node value in forward order. while (current != nullptr) { cout << current->data; if (current->next != nullptr) { cout << " "; } current = current->next; } cout << "\n";}// Driver code.int main() { vector<int> values = {2, 5, 8, 7}; int value = 10; Node* head = createList(values); Solution sol; head = sol.insertNewHead(head, value); printList(head); return 0;}Complexity Analysis
Time Complexity: O(1), head insertion uses only constant-time node creation and pointer update.
Space Complexity: O(1), only one new node is created and no auxiliary structure grows with input size.
Interview follow-up Questions
No. Head insertion changes only the front pointer, so no traversal loop is required.
Be the first to add a comment.