Linked List Insertion At Beginning

Summary

This problem involves inserting a new node at the beginning of a linked list. The key concept involved is manipulating nodes in a linked data structure, specifically adding a new element to the start of the list.

Detailed Explanation

The goal is to insert a new node with some given value at the beginning of the linked list. To achieve this, we need to update the next pointer of the existing head node and then assign the new node as the new head node. The time complexity for this problem is O(1) since we are not traversing the entire list.

Here's a step-by-step breakdown:

1. Create a new node with the given value.
2. Update the next pointer of the existing head node to point to the new node (i.e., make the new node the new head).
3. Set the head of the linked list to the new node.

Optimized Solutions

Java

java
public class LinkedList {
    public void insertAtBeginning(int value, Node head) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }
}

Python

python
class LinkedList:
    def insert_at_beginning(self, value, head):
        new_node = Node(value)
        if head is None:
            head = new_node
        else:
            new_node.next = head
            head = new_node
        return head

C++

cpp
class LinkedList {
public:
    void insertAtBeginning(int value, Node* &head) {
        Node* newNode = new Node(value);
        if (*head == nullptr) {
            *head = newNode;
        } else {
            newNode->next = *head;
            *head = newNode;
        }
    }
};

JavaScript

javascript
class LinkedList {
  insertAtBeginning(value, head) {
    const newNode = { value, next: null };
    if (head === null) {
      this.head = newNode;
    } else {
      newNode.next = head;
      this.head = newNode;
    }
  }
}