Delete Node of Linked List From Different Position

Understanding Linked Lists

A linked list is a linear data structure composed of nodes, where each node contains data and a pointer (or reference) to the next node in the sequence. Unlike arrays, linked lists provide dynamic memory allocation, allowing efficient insertion and deletion of elements without the need to shift other elements.

This article contains deletion of the node of linked list at various position:

Deletion of head node
Deletion of tail node
Deletion of node from any position

1️⃣ Problem Statement

Given a singly linked list, we aim to delete the head node of the list.

Examples

Example1:

Input: list: 1 -> 2 -> 3
Output: list: 2 -> 3

Understanding the Head Node

The head node of a linked list is the first node in the sequence. The head is a critical reference point as it provides access to the entire list. Deleting the head node means removing this first node and ensuring the list remains intact and accessible through the new head node.

Steps to Delete the Head Node

To delete the head node of a singly linked list, follow these steps:

Check if the List is Empty: Before attempting to delete, ensure that the linked list is not empty. If it is, there is no head node to delete.
Update the Head Pointer: Change the head pointer to point to the second node in the list, effectively bypassing the current head.
Delete the Original Head Node: Free the memory occupied by the original head node to prevent memory leaks.

Edge Cases to Consider

When deleting the head node of a linked list, consider the following edge cases:

Empty List: Attempting to delete from an empty list should be handled gracefully without causing errors.
Single Node List: If the list contains only one node, deleting the head node will result in an empty list. Ensure the head pointer is updated to nullptr.
Multiple Deletes: If multiple deletions occur consecutively, ensure that each deletion properly updates the head pointer and frees memory.

Code:

#include <iostream>
using namespace std;

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

void deleteHead(ListNode*& head) {
    // Step 1: Check if the list is empty
    if (head == nullptr) {
        cout << "The list is empty. Nothing to delete." << endl;
        return;
    }

    // Step 2: Update the head pointer to the next node
    ListNode* temp = head;
    head = head->next;

    // Step 3: Delete the original head node
    delete temp;
}

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

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

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

    // Delete the head node
    deleteHead(head);

    cout << "List after deleting the head node: ";
    printList(head);

    return 0;
}

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

// Node structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int data1): val(data1), next(nullptr) {}
    ListNode(int data1, ListNode *next1): val(data1), next(next1) {}
};

class Solution {
public:
    // Function to delete the head node of the linked list
    ListNode* deleteHead(ListNode* head) {
        // If list is empty, nothing to delete
        if (head == nullptr) 
            return nullptr; 
        
        // Set temporary pointer
        ListNode* temp = head; 
        
        // Update head to the next node 
        head = head->next;  
        
        // Delete original head    
        delete temp; 
        
        // Return new head          
        return head;           
    }
};

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

// Function to insert a new node at the beginning of the linked list
ListNode* insertAtHead(ListNode* head, int data) {
    ListNode* newNode = new ListNode(data);
    newNode->next = head;
    head = newNode;
    return head;
}

int main() {
    // Create a linked list
    ListNode* head = nullptr;
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);

    cout << "Original list: ";
    printList(head);
    
    // Creating an instance of Solution Class
    Solution sol;
    
    // Function call to delete the head node
    head = sol.deleteHead(head);

    cout << "List after deleting head: ";
    printList(head);

    return 0;
}

Complexity Analysis

Time Complexity:O(1)
- Since in order to delete the very first node doesn't involve traversing the linked list. Thus it has the constant-time complexity.
Space Complexity:O(1)
- The space required does not depend on the size of the linked list but is fixed (a single pointer variable). Thus the space complexity of deleting the head node of a linked list is also constant.

2️⃣ Problem Statement

Given a linked list, we aim to delete the tail node of the list.

Examples

Example1:

Input: list: 1 -> 2 -> 3
Output: list: 1 -> 2

Example2:

Input: list: 1 -> 2
Output: list: 1

Example3:

Input: list: 1
Output: list:

Understanding the Tail Node in a Linked List

A linked list is a linear data structure where each node points to the next, forming a chain. The tail node is the last node in the list and points to nullptr, indicating the end of the list. Deleting the tail node involves removing this last element and ensuring the new last node correctly points to nullptr.

Steps to Delete the Tail Node

To delete the tail node of a singly linked list, follow these steps:

Check if the List is Empty: Ensure the linked list is not empty. If it is, there is no tail node to delete.
Check if the List has Only One Node: If the list contains only one node, deleting the tail node will result in an empty list.
Traverse the List to Find the Second-to-Last Node: Start from the head and iterate through the list to find the node right before the tail node.
Update the Second-to-Last Node's Pointer: Set the next pointer of the second-to-last node to nullptr, making it the new tail.
Delete the Original Tail Node: Free the memory occupied by the original tail node to prevent memory leaks.

Edge Cases to Consider

When deleting the tail node of a linked list, consider the following edge cases:

Empty List: If the list is empty, there is no tail to delete. This should be handled gracefully.
Single Node List: If the list contains only one node, deleting the tail node will result in an empty list. Make sure to set head to nullptr.
Multiple Deletes: Ensure that multiple deletions do not cause errors, especially after the list becomes empty.

Code:

#include <iostream>

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

void deleteTail(ListNode*& head) {
    // Step 1: Check if the list is empty
    if (head == nullptr) {
        std::cout << "The list is empty. Nothing to delete." << std::endl;
        return;
    }

    // Step 2: Check if the list has only one node
    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }

    // Step 3: Traverse to find the second-to-last node
    ListNode* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }

    // Step 4: Update the second-to-last node's pointer to nullptr
    ListNode* temp = current->next;
    current->next = nullptr;

    // Step 5: Delete the original tail node
    delete temp;
}

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 1 -> 2 -> 3 -> nullptr
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

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

    // Delete the tail node
    deleteTail(head);

    std::cout << "List after deleting the tail node: ";
    printList(head);

    return 0;
}

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

// Node structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int data1): val(data1), next(nullptr) {}
    ListNode(int data1, ListNode *next1): val(data1), next(next1) {}
};

class Solution {
public:
    // Function to delete the tail node of linked list 
    ListNode* deleteTail(ListNode* head) {
        
        // If the list is empty or has only one node
        if (head == NULL || head->next == NULL)
            return NULL; // Return NULL
        
        // Temporary pointer
        ListNode* temp = head;
        
        /*Traverse to the second last
        node in the list*/
        while (temp->next->next != NULL) {
            temp = temp->next;
        }
        
        // Delete the last node
        delete temp->next;
        
        /*Set the next of the second 
        last node to nullptr, 
        effectively removing the last node*/
        temp->next = nullptr;
        
        // Return head of modified list
        return head;
    }
};

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

// Function to insert a new node at the beginning of the linked list
ListNode* insertAtHead(ListNode* head, int data) {
    ListNode* newNode = new ListNode(data);
    newNode->next = head;
    head = newNode;
    return head;
}

int main() {
    // Create a linked list
    ListNode* head = nullptr;
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);

    cout << "Original list: ";
    printList(head);
    
    // Creating an instance of Solution Class
    Solution sol;
    
    // Function call to delete the tail node
    head = sol.deleteTail(head);

    cout << "List after deleting head: ";
    printList(head);

    return 0;
}

Complexity Analysis

Time Complexity: O(n)
- To delete the tail node, we must traverse the list to find the second-to-last node. The traversal takes linear time in the size of the list (n).
Space Complexity: O(1)O(1)O(1)
- The operation uses a fixed amount of additional space (a few pointer variables) regardless of the list size.

3️⃣ Problem Statement

Given a singly linked list and an integer position n, delete the node at the nth position (0-indexed) from the list.

Examples

Example 1:

Let's consider a singly linked list:
head -> 1 -> 2 -> 3 -> 4 -> 5

If we want to delete the node at position 2 (0-indexed):

The node with value 3 should be deleted.
The updated list should be: head -> 1 -> 2 -> 4 -> 5

Edge Cases to Consider

When deleting a node from a specific position, consider the following edge cases:

Empty List: If the list is empty, any deletion request should be handled gracefully.
Invalid Position: If the position is negative or exceeds the length of the list, output an error message and avoid any deletion.
First Position (Head Node): If the position is 0, handle the deletion of the head node separately.
Position Out of Bounds: If the position is greater than or equal to the length of the list, no deletion should occur.

Approach

To delete an element from a specified position in a singly linked list, follow these steps:

Check if the List is Empty: If the linked list is empty, there are no elements to delete.
Check if the Position is Valid: Ensure the given position is within the bounds of the list.
Delete the Head Node if Position is 0: If the position is 0 (the first element), update the head pointer to point to the next node and delete the current head.
Traverse to the Node Before the Given Position: Start from the head and move to the node just before the specified position.
Update the Pointer of the Previous Node: Set the next pointer of the previous node to skip the node to be deleted.
Delete the Node: Free the memory occupied by the node to prevent memory leaks.

Code

#include <iostream>

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

void deleteNodeAtPosition(ListNode*& head, int position) {
    // Step 1: Check if the list is empty
    if (head == nullptr) {
        std::cout << "The list is empty. Nothing to delete." << std::endl;
        return;
    }

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

    // Step 3: If the position is 0, delete the head node
    if (position == 0) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }

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

    // Step 5: Check if current or current->next is null
    if (current == nullptr || current->next == nullptr) {
        std::cout << "Position exceeds the length of the list. Cannot delete." << std::endl;
        return;
    }

    // Step 6: Delete the node at the given position
    ListNode* temp = current->next;
    current->next = temp->next;
    delete temp;
}

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 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

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

    // Delete the node at position 2 (0-based index)
    deleteNodeAtPosition(head, 2);

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

    return 0;
}

OR:

/*
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;
    }
};
*/

class Solution {
public:
    // Function to delete the k-th node in the linked list
    ListNode* deleteKthNode(ListNode* &head, int k) {
        // Case 1: If the k-th node is the head (first element)
        if (k == 1) {
            // Check if the list is empty or has only one node
            if (head == nullptr || head->next == nullptr) {
                return nullptr; // If so, return null
            }
            // If more than one node, delete the head
            ListNode* toBeDelete = head; // Temporarily store the head node
            head = head->next;          // Move head pointer to the next node

            delete toBeDelete;          // Free memory of the old head node
            return head;                // Return the new head
        }

        // Initialize a counter and an iterator to traverse the list
        int count = 1;
        ListNode* iterator = head;

        // Traverse the list to reach the (k-1)-th node
        while (iterator->next != nullptr) {
            if (count == k - 1) {
                break; // Stop when the (k-1)-th node is found
            }
            iterator = iterator->next; // Move to the next node
            count++;
        }

        // Temporarily store the k-th node to be deleted
        ListNode* toBeDelete = iterator->next;

        // Update the next pointer of the (k-1)-th node to skip the k-th node
        iterator->next = toBeDelete->next;

        // Free the memory of the k-th node
        delete toBeDelete;

        // Return the head of the modified list
        return head;
    }
};

Complexity Analysis

Time Complexity: O(n)
- To delete a node at a specific position, we need to traverse 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️⃣ Delete the element with value X

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

Examples:

Example 1:

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

Explanation: The last node has the value equivalent to
4, so it is deleted.

Example 2:

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

Explanation: There is node whose value is equal to 1.
So no nodes is removed.

Intuition:

Traverse the linked list and check if the data in the current node matches the given value. If a match is found, remove this node by updating the previous node's next reference to point to the node following the current one. If the traversal completes without finding a match, the linked list remains unchanged.

Approach:

Initialize a pointer to the head of the list and another to null. The first pointer will traverse the list, while the second keeps track of the node before the current node.
Traverse the linked list until the data in the current node matches the target value. Consider two scenarios:
1. If a match is found:
  1. Update the previous node’s reference to point to the node following the current one.
  2. Release the memory occupied by the current node, effectively removing it from the list.
2. If the traversal completes without finding a match:
  1. No changes are made to the linked list.

Code:

/*
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;
    }
};
*/

class Solution {
public:
    // Function to delete the first node with value X from the linked list
    ListNode* deleteNodeWithValueX(ListNode* &head, int X) {
        // Handle the case where the list is empty
        if (head == nullptr) {
            return nullptr;
        }

        // Case 1: If the node to delete is the head node
        if (head->val == X) {
            ListNode* toBeDelete = head; // Store the current head
            head = head->next;          // Update the head to the next node
            delete toBeDelete;          // Free the memory
            return head;                // Return the updated head
        }

        // Case 2: Traverse the list to find the node with value X
        ListNode* current = head;
        ListNode* prev = nullptr;

        while (current != nullptr && current->val != X) {
            prev = current;          // Keep track of the previous node
            current = current->next; // Move to the next node
        }

        // If we found the node with value X
        if (current != nullptr) {
            prev->next = current->next; // Skip the current node
            delete current;             // Free the memory
        }

        // Return the updated head of the list
        return head;
    }
};

Complexity Analysis:

Time Complexity: O(N) worst case, when the value is found at the tail, and O(1) best case, when the value is found at the head. Here N is the length of the linked list.
Space Complexity: O(1) as no extra space used

Understanding Linked Lists

1️⃣ Problem Statement

Examples

Understanding the Head Node

Steps to Delete the Head Node

Edge Cases to Consider

Code:

Complexity Analysis

2️⃣ Problem Statement

Examples

Understanding the Tail Node in a Linked List

Steps to Delete the Tail Node

Edge Cases to Consider

Code:

Complexity Analysis

3️⃣ Problem Statement

Examples

Edge Cases to Consider

Approach

Code

OR:

Complexity Analysis

4️⃣ Delete the element with value X

Examples:

Intuition:

Approach:

Code:

Complexity Analysis:

About me

Popular Posts

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory

Quick links

Tags

Newsletter

🛠️ Settings

Understanding Linked Lists

1️⃣ Problem Statement

Examples

Understanding the Head Node

Steps to Delete the Head Node

Edge Cases to Consider

Code:

Complexity Analysis

2️⃣ Problem Statement

Examples

Understanding the Tail Node in a Linked List

Steps to Delete the Tail Node

Edge Cases to Consider

Code:

Complexity Analysis

3️⃣ Problem Statement

Examples

Edge Cases to Consider

Approach

Code

OR:

Complexity Analysis

4️⃣ Delete the element with value X

Examples:

Intuition:

Approach:

Code:

Complexity Analysis:

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory