1️⃣ Insert Node at the beginning (at Head)

Problem Statement:

Given a linked list, we want to insert a new node at the beginning of the list.

Examples:

Example 1:

Input: List = 2 -> 3 -> 4 -> 5 -> nullptr, Node = 1
Output: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

Approach:

To insert a node a the beginning of a linked list, we need to follow these steps:

1. Allocate memory for the new node.
2. Set the data of the new node.
3. Set the next pointer of the next node to point to the current head of the list.
4. Update the head pointer to point to the new node.

Algorithm:

1. Create a new node with the given data.
2. If the head pointer is null, set the head pointer to the new node and return.
3. Set the next pointer of the new node to point to the current head of the list.
4. Update the head pointer to point to the new node.

Code

#include <bits/stdc++.h>

using namespace std;

class ListNode {
  public:
    int val;
  ListNode * next;
  ListNode(int x) {
    val = x;
    next = NULL;
  }
};

void PrintList(ListNode * head) // Function to print the LinkedList
{
  ListNode * curr = head;
  for (; curr != NULL; curr = curr -> next)
    cout << curr -> val << "-->";
  cout << "null" << endl;
}

ListNode * InsertatFirst(int value, ListNode * head) {

  // Step1 : creating a new Node with the given val
  ListNode * newnode = new ListNode(value);

  // Step2 : Making next of newly created Node to point the head of LinkedList
  newnode -> next = head;

  // Making the newly created Node as head
  head = newnode;
  return head;
}

int main() {
  ListNode * head = NULL; // head of the LinkedList
  head = InsertatFirst(5, head);
  head = InsertatFirst(4, head);
  head = InsertatFirst(3, head);
  head = InsertatFirst(2, head);
  
  cout << "LinkedList before inserting 0 at beginning : " << endl;
  PrintList(head);
  head = InsertatFirst(1, head);
  cout << "LinkedList after inserting 0 at beginning : " << endl;
  PrintList(head);
  return 0;
}

// Output
LinkedList before inserting 0 at beginning : 
2 --> 3 --> 4 --> 5 --> nullptr
LinkedList after inserting 0 at beginning : 
1 --> 2 --> 3 --> 4 --> 5 --> nullptr

Complexity Analysis

• Time Complexity: O(1)
  • The insertion operation at the beginning of a linked list involves constant time operations such as memory allocation, setting data and pointer values, and updating the head pointer. These operations do not depend on the size of the linked list, so the time complexity remains constant.
• Space Complexity: O(1)
  • The space complexity of the insertion operation at the beginning of a linked list is constant because it requires only a constant amount of additional memory for creating the new node, regardless of the size of the linked list.

2️⃣ Insert Node at the end (Tail)

Problem Statement:

Given a linked list, we want to insert a new node at the end of the list.

Examples

Example 1:

Input: List = 2 -> 3 -> 4 -> 5 -> nullptr, Node = 6
Output: 2 -> 3 -> 4 -> 5 -> 6 -> nullptr

Steps

To insert a node at the end of a singly linked list, follow these steps:

1. Create a New Node: Allocate memory for the new node and set its data and next pointer to nullptr.
2. Check if the List is Empty: If the linked list is empty, make the new node the head node.
3. Traverse the List to Find the Last Node: Start from the head and move to the last node whose next pointer is nullptr.
4. Update the Last Node's Next Pointer: Set the next pointer of the last node to point to the new node.

Edge Cases to Consider

When inserting a node at the end of a linked list, consider the following edge cases:

1. Empty List: If the list is empty, the new node becomes the head node.
2. Single Node List: If the list contains only one node, the new node is simply added after it.
3. Multiple Insertions: Ensure that multiple insertions work correctly without corrupting the list structure.

Code

#include <iostream>

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int x) : data(x), next(nullptr) {}
};

// Function to insert a node at the end of the linked list
void insertAtEnd(ListNode*& head, int data) {
    // Step 1: Create a new node
    ListNode* newNode = new ListNode(data);
    
    // Step 2: Check if the list is empty
    if (head == nullptr) {
        head = newNode;
        return;
    }

    // Step 3: Traverse to the end of the list
    ListNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }

    // Step 4: Update the last node's next pointer to point to the new node
    current->next = newNode;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->data << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

int main() {
    // Create a simple linked list with initial elements
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    std::cout << "Original list: ";
    printList(head);

    // Insert a new node at the end
    insertAtEnd(head, 4);

    std::cout << "List after inserting at the end: ";
    printList(head);

    return 0;
}

Complexity Analysis

• Time Complexity:  O(n)
  • To insert a node at the end, we need to traverse the entire list to find the last node, which takes linear time in the size of the list (n).
• Space Complexity: O(1)
  • The operation uses a fixed amount of additional space (a few pointer variables) regardless of the list size.

3️⃣ Insert at any position

Problem Statement

Given a linked list, we want to insert a new node at the specified position.

Steps:

To insert a node at a specific position in a singly linked list, follow these steps:

1. Create a New Node: Allocate memory for the new node, set its data, and initialize its next pointer to nullptr.
2. Check if the List is Empty: If the list is empty and the position is 0, make the new node the head.
3. Check if the Position is Valid: Ensure the given position is within the valid range (0 to the current length of the list).
4. Insert at the Head if Position is 0: Update the head pointer to point to the new node, and set the new node's next pointer to the old head.
5. Traverse to the Node Before the Desired Position: Start from the head and move to the node just before the specified position.
6. Update Pointers to Insert the New Node: Adjust the pointers to insert the new node at the desired position.

Edge Cases to Consider

When inserting a node at any position in a linked list, consider the following edge cases:

1. Empty List: If the list is empty and the position is 0, the new node should become the head.
2. Invalid Position: If the position is negative or exceeds the length of the list, the function should handle it gracefully without making any changes.
3. Head Insertion: If the position is 0, the function should insert the new node as the head of the list.
4. Position Out of Bounds: If the position is greater than the length of the list, the function should avoid insertion and output an appropriate message.

Code

#include <iostream>

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int x) : data(x), next(nullptr) {}
};

// Function to insert a node at a specific position in the linked list
void insertAtPosition(ListNode*& head, int data, int position) {
    // Step 1: Create a new node
    ListNode* newNode = new ListNode(data);

    // Step 2: Check if the position is valid
    if (position < 0) {
        std::cout << "Invalid position. Position should be a non-negative integer." << std::endl;
        delete newNode;
        return;
    }

    // Step 3: Insert at the head if the position is 0
    if (position == 0) {
        newNode->next = head;
        head = newNode;
        return;
    }

    // Step 4: Traverse to the node before the desired position
    ListNode* current = head;
    for (int i = 0; current != nullptr && i < position - 1; ++i) {
        current = current->next;
    }

    // Step 5: Check if current is null (position is out of range)
    if (current == nullptr) {
        std::cout << "Position exceeds the length of the list. Cannot insert." << std::endl;
        delete newNode;
        return;
    }

    // Step 6: Update pointers to insert the new node
    newNode->next = current->next;
    current->next = newNode;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->data << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

int main() {
    // Create a simple linked list with initial elements
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    std::cout << "Original list: ";
    printList(head);

    // Insert a new node with data 4 at position 2 (0-based index)
    insertAtPosition(head, 4, 2);

    std::cout << "List after inserting at position 2: ";
    printList(head);

    // Insert a new node with data 0 at position 0 (head insertion)
    insertAtPosition(head, 0, 0);

    std::cout << "List after inserting at position 0: ";
    printList(head);

    return 0;
}

Complexity Analysis

• Time Complexity: O(n)
  • Inserting a node at a specific position requires traversing the list up to that position, which takes linear time in the size of the list (n).
• Space Complexity: O(1)
  • The operation uses a fixed amount of additional space (a few pointer variables) regardless of the size of the list.

4️⃣ Insertion before the value X

Given the head of a singly linked list and two integers X and val, insert a node with the value val before the node with value X in the linked list and return the head of the modified list.

Example 1:

Input: head->1->2->3, X = 2, val = 5
Output: head->1->5->2->3

Explanation: The node with value 5 is inserted before the node with value 2.

Example 2:

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

Explanation: As the node with value 4 does not exists, so no new node is inserted.

Intuition:

Find the node with the given value in the linked list and then insert the newly created node with data before the given node.

Approach:

1. Initialize a temporary pointer to traverse the list.
2. Traverse the list until you find a node whose next node has the target value, since the new node needs to be inserted before this node.
3. Once you find the correct position, create a new node with the given value.
4. To insert the new node:
   1. Point the new node to the next node in the list.
   2. Update the current node to point to the new node, completing the insertion.
5. If the traversal completes without finding the target value, it means the target value is not in the list, i.e., no insertion will occur.

Code:

/*
Definition of singly linked list:
struct ListNode
{
    int val; // Value of the node
    ListNode *next; // Pointer to the next node
    ListNode(int data1) // Constructor to initialize a node with a value
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1) // Constructor to initialize a node with a value and a next pointer
    {
        val = data1;
        next = next1;
    }
};
*/

class Solution {
public:
    // Function to insert a node with value `val` before the first occurrence of a node with value `X`
    ListNode* insertBeforeX(ListNode* &head, int X, int val) {
        // Create a new node with the given value `val`
        ListNode* newNode = new ListNode(val);

        // Case 1: If the list is empty, return the new node as the head
        if (head == nullptr) {
            return newNode;
        }

        // Case 2: If the first node itself has the value `X`
        if (head->val == X) {
            newNode->next = head; // Link the new node to the current head
            return newNode;       // Return the new node as the updated head
        }

        // Initialize pointers to traverse the list
        ListNode* prev = nullptr; // Pointer to keep track of the previous node
        ListNode* current = head; // Pointer to traverse the list

        bool isFound = false; // Flag to indicate if a node with value `X` is found

        // Traverse the list to find the first occurrence of `X`
        while (current != nullptr) {
            if (current->val == X) { // Check if the current node has value `X`
                isFound = true;
                break; // Exit the loop as we found the target node
            }
            prev = current;          // Update `prev` to the current node
            current = current->next; // Move to the next node
        }

        // If a node with value `X` is found
        if (isFound) {
            newNode->next = prev->next; // Link the new node to the current node
            prev->next = newNode;      // Update the previous node's next to point to the new node
        }

        // Return the head of the list (unchanged if `X` was not found)
        return head;
    }
};

Complexity Analysis:

• Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
• Space Complexity: O(1) as we have not used any extra space.