Problem Statement

Given the head of a singly linked list, your task is to delete the entire linked list to free up the memory used by the nodes. After deletion, the head pointer should be set to nullptr to indicate that the list is now empty.

Examples

Example 1:

Input: 10 -> 20 -> 30 -> 40 -> nullptr
Output: Linked list deleted. Head is now nullptr.

Example 2:

Input: 5 -> nullptr
Output: Linked list deleted. Head is now nullptr.

Example 3:

Input: nullptr
Output: Linked list deleted. Head is now nullptr.

Approaches

1️⃣ Traversing

Approach:

1. Initialization: Start from the head of the linked list.
2. Traversal and Deletion: Use a loop to traverse the linked list. For each node, perform the following:
   • Store the next node in a temporary pointer.
   • Delete the current node to free its allocated memory.
   • Move to the next node using the temporary pointer.
3. Nullify Head: After the loop ends, set the head pointer to nullptr to indicate that the linked list is empty.

Code:

#include <iostream>
using namespace std;

class ListNode {
public:
    int data;
    ListNode* next;

    ListNode(int val) : data(val), next(nullptr) {}
};

// Function to delete the entire linked list
void deleteLinkedList(ListNode*& head) {
    ListNode* current = head;
    ListNode* nextNode = nullptr;

    // Traverse through the linked list
    while (current != nullptr) {
        nextNode = current->next;  // Save the next node
        delete current;            // Delete the current node
        current = nextNode;        // Move to the next node
    }

    head = nullptr;  // Set head to nullptr, indicating the list is now empty
}

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

// Example usage
int main() {
    // Creating a sample linked list: 10 -> 20 -> 30 -> 40
    ListNode* head = new ListNode(10);
    head->next = new ListNode(20);
    head->next->next = new ListNode(30);
    head->next->next->next = new ListNode(40);

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

    // Delete the entire linked list
    deleteLinkedList(head);

    cout << "Linked list after deletion: ";
    printList(head);  // This should print "nullptr"

    return 0;
}

Complexity Analysis:

• Time Complexity:
  • O(n), where n is the number of nodes in the linked list. This is because each node is visited exactly once and then deleted.
• Space Complexity:
  • O(1), as no additional space proportional to the input size is used; only a few extra variables (current and nextNode) are used.