Insertion at the head of LL

Linked-List Fundamentals (Single LL) Easy

Given the head of a singly linked list and an integer X, insert a node with value X at the head of the linked list and return the head of the modified list.

The head is the first node of the linked list.

Examples:

Input: head -> 1 -> 2 -> 3, X = 7

Output: head -> 7 -> 1 -> 2 -> 3

Explanation: 7 was added as the 1st node.

Input: head, X = 7

Output: head -> 7

Explanation: 7 was added as the 1st node.

Input: head -> 1 -> 3, X = 4

Constraints

0 <= number of nodes in the Linked List <= 1000
0 <= ListNode.val <= 100
0 <= X <= 100

Hints

Create a new node with value X. Set the next pointer of the new node to the current head.
Update the head pointer to point to the new node, making it the first node of the list.

Company Tags

DoorDash Oracle Twilio Seagate Technology Shopify Cerner Qualcomm Teladoc Health Riot Games Roche Databricks JPMorgan Chase Johnson & Johnson MongoDB Goldman Sachs Flipkart Siemens Healthineers Byju's Docker Rakuten HashiCorp Chewy ARM Zynga Optum TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Insert at the head of a linked list by creating a new node, linking it to the current head, and updating the head pointer.

Approach:

Create a new node with the value to be inserted at the beginning of the linked list.
Set the new node's pointer to the current head of the linked list.
Update the head of the linked list to the newly created node.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

// Solution class
class Solution {
public:
    // Function to insert at head
    ListNode* insertAtHead(ListNode* head, int X) {
        //Creating a new node 
        ListNode* newnode = new ListNode(X);
        
        /*Making next of newly created node to 
        point the head of the LinkedList*/
        newnode->next = head;
        
        // Making newly created node as head
        head = newnode;
        
        // Return the head of modified list
        return head;
    }
};


// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create a linked list from a vector
    vector<int> arr = {20, 30, 40};
    int X= 10;
    ListNode* head = new ListNode(arr[0]);
    head->next = new ListNode(arr[1]);
    head->next->next = new ListNode(arr[2]);
    
    // Print the original list
    cout << "Original List: ";
    printLL(head);
    
    // Create a Solution object 
    Solution sol;
    head = sol.insertAtHead(head, X);

    // Print the modified linked list
    cout << "List after inserting the given value at head: ";
    printLL(head);

    return 0;
}
import java.util.*;

// Definition of singly linked list
class ListNode {
    int val;
    ListNode next;

    ListNode(int data1) {
        val = data1;
        next = null;
    }

    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

// Solution class
class Solution {
    // Function to insert at head
    public ListNode insertAtHead(ListNode head, int X) {
        // Creating a new node 
        ListNode newnode = new ListNode(X);
        
        /* Making next of newly created node to 
        point to the head of the LinkedList */
        newnode.next = head;
        
        // Making newly created node as head
        head = newnode;
        
        // Return the head of modified list
        return head;
    }
}

// Main class
class Main {
    // Helper method to print the linked list
    private static void printLL(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Create a linked list from an array
        int[] arr = {20, 30, 40};
        int X= 10;
        ListNode head = new ListNode(arr[0]);
        head.next = new ListNode(arr[1]);
        head.next.next = new ListNode(arr[2]);

        // Print the original list
        System.out.print("Original List: ");
        printLL(head);

        // Create a Solution object
        Solution sol = new Solution();
        head = sol.insertAtHead(head, X);

        // Print the modified linked list
        System.out.print("List after inserting the given value at head: ");
        printLL(head);
    }
}
# Definition of singly linked list
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to insert at head
    def insertAtHead(self, head, X):
        # Creating a new node
        newnode = ListNode(X)
        
        ''' Making next of newly created node to 
        point to the head of the LinkedList '''
        newnode.next = head
        
        # Making newly created node as head
        head = newnode
        
        # Return the head of modified list
        return head

# Helper Function to print the linked list
def printLL(head):
    while head is not None:
        print(head.val, end=" ")
        head = head.next
    print()

if __name__ == "__main__":
    # Create a linked list from a list
    arr = [20, 30, 40]
    X= 10
    head = ListNode(arr[0])
    head.next = ListNode(arr[1])
    head.next.next = ListNode(arr[2])

    # Print the original list
    print("Original List: ", end="")
    printLL(head)

    # Create a Solution object
    sol = Solution()
    head = sol.insertAtHead(head, X)

    # Print the modified linked list
    print("List after inserting the given value at head: ", end="")
    printLL(head)
// Definition of singly linked list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

// Solution class
class Solution {
    // Function to insert at head
    insertAtHead(head, X) {
        // Creating a new node
        let newnode = new ListNode(X);
        
        /* Making next of newly created node to 
        point to the head of the LinkedList */
        newnode.next = head;
        
        // Making newly created node as head
        head = newnode;
        
        // Return the head of modified list
        return head;
    }
}

// Helper Function to print the linked list
function printLL(head) {
    let current = head;
    while (current !== null) {
        process.stdout.write(current.val + " ");
        current = current.next;
    }
    console.log();
}

// Main function
let arr = [20, 30, 40];
let X= 10;
let head = new ListNode(arr[0]);
head.next = new ListNode(arr[1]);
head.next.next = new ListNode(arr[2]);

// Print the original list
console.log("Original List: ");
printLL(head);

// Create a Solution object
let sol = new Solution();
head = sol.insertAtHead(head, X);

// Print the modified linked list
console.log("List after inserting the given value at head: ");
printLL(head);

Complexity Analysis:

Time Complexity: O(1) for inserting the new node at the head of the linked list Space Complexity: O(1) no extra space used.

Code

Problem List