Problem Description

LeetCode Problem Link: 707. Design Linked List

You can choose to use a singly linked list or a doubly linked list to design and implement your own linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If it is a doubly linked list, you also need the attribute prev to indicate the previous node in the list. Assume all node indices in the linked list start from 0.

Implement the MyLinkedList class:

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the index-th node in the linked list. If the index is invalid, return -1.
• void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the index-th node in the linked list. If index equals the length of the linked list, the node will be apended to the end of the linked list. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) Delete the index-th node in the linked list, if the index is valid.

Example:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

• 0 <= index, val <= 1000
• Please do not use the built-in LinkedList library.
• The number of calls to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex will not exceed 2000.

Solution Using a Dummy Head Node

Code

class MyLinkedList {
private:
    // Define the structure for a linked list node
    struct ListNode {
        int value;
        ListNode* nextNode;
        ListNode(int val) : value(val), nextNode(nullptr) {}
    };

    ListNode* dummyHead; // Dummy head node to simplify edge case handling
    int listSize;        // Current size of the linked list

public:
    // Constructor: Initialize the linked list with a dummy head
    MyLinkedList() {
        dummyHead = new ListNode(0); // Dummy head's value is irrelevant
        listSize = 0;
    }

    // Get the value of the node at the specified index
    int get(int index) {
        // Check for invalid index
        if (index < 0 || index >= listSize) {
            return -1;
        }
        ListNode* current = dummyHead->nextNode; // Start from the first real node
        // Traverse to the desired index
        while (index--) {
            current = current->nextNode;
        }
        return current->value;
    }

    // Insert a new node at the head of the list
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->nextNode = dummyHead->nextNode; // New node points to old first node
        dummyHead->nextNode = newNode;          // Dummy head points to new node
        ++listSize;
    }

    // Append a new node at the tail of the list
    void addAtTail(int val) {
        ListNode* newNode = new ListNode(val);
        ListNode* current = dummyHead;
        // Traverse to the last node
        while (current->nextNode != nullptr) {
            current = current->nextNode;
        }
        current->nextNode = newNode; // Link the last node to the new node
        ++listSize;
    }

    // Insert a new node before the node at the specified index
    void addAtIndex(int index, int val) {
        // If index is greater than size, do not insert
        if (index > listSize) {
            return;
        }
        // If index is negative, treat it as inserting at head
        if (index < 0) {
            index = 0;
        }
        ListNode* newNode = new ListNode(val);
        ListNode* current = dummyHead;
        // Traverse to the node before the insertion point
        while (index--) {
            current = current->nextNode;
        }
        // Standard insertion logic
        newNode->nextNode = current->nextNode;
        current->nextNode = newNode;
        ++listSize;
    }

    // Delete the node at the specified index
    void deleteAtIndex(int index) {
        // Check for invalid index
        if (index < 0 || index >= listSize) {
            return;
        }
        ListNode* current = dummyHead;
        // Traverse to the node before the one to be deleted
        while (index--) {
            current = current->nextNode;
        }
        ListNode* nodeToDelete = current->nextNode;
        current->nextNode = current->nextNode->nextNode; // Bypass the node to delete
        delete nodeToDelete; // Free memory
        nodeToDelete = nullptr; // Avoid dangling pointer
        --listSize;
    }

    // Optional: Helper function to print the list (for debugging)
    void printList() {
        ListNode* current = dummyHead->nextNode;
        while (current != nullptr) {
            std::cout << current->value << " ";
            current = current->nextNode;
        }
        std::cout << std::endl;
    }

    // Destructor (important to prevent memory leaks)
    ~MyLinkedList() {
        ListNode* current = dummyHead;
        while (current != nullptr) {
            ListNode* nextNode = current->nextNode;
            delete current;
            current = nextNode;
        }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

Complexity Analsyis

• Time Complexity:
  • Operations involving an index (get, addAtIndex, deleteAtIndex) have a time complexity of O(index) due to traversal.
  • Operations at the head (addAtHead) and tail (addAtTail) have a time complexity of O(1) and O(n) respectively, where n is the list size for tail insertion due to traversal.
• Space Complexity: O(n), where n is the number of nodes in the list, for storing the nodes.