[/dsa/leetcode]

707 - Design Linked List

Friday, 18 September 2026

<medium> [problem]

Hang a dummy node in front of the list so every operation becomes the same walk to the node before the target, then one rewire.

{linked list}{design}

Problem

Design your implementation of the linked list. You can choose to use a singly or doubly linked list. A node in a singly linked list should have two attributes: val and next, where next is a pointer to the next node.

Implement the MyLinkedList class:

  • MyLinkedList() initializes the object.
  • int get(int index) returns the value of the indexth node, or -1 if the index is invalid.
  • void addAtHead(int val) adds a node before the first element.
  • void addAtTail(int val) appends a node at the end.
  • void addAtIndex(int index, int val) inserts a node before the indexth node. If index equals the length the node is appended; if index is greater than the length nothing happens.
  • void deleteAtIndex(int index) deletes the indexth node if the index is valid.
Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 2]

Constraints:

  • 0 <= index, val <= 1000
  • Do not use the built-in linked list library
  • At most 2000 calls will be made in total

Approach

class MyLinkedList {
private:
    struct Node {
        int val;
        Node* next;
        Node(int d) : val(d), next(nullptr) {}
    };
    Node* head;
    int size;

public:
    MyLinkedList() : head(new Node(0)), size(0) {}

    ~MyLinkedList() {
        Node* curr = head;
        while (curr) {
            Node* temp = curr->next;
            delete curr;
            curr = temp;
        }
    }

    int get(int index) {
        if (index < 0 || index >= size)
            return -1;
        Node* curr = head->next;
        while (index--)
            curr = curr->next;
        return curr->val;
    }

    void addAtHead(int val) { addAtIndex(0, val); }

    void addAtTail(int val) { addAtIndex(size, val); }

    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        Node* prev = head;
        while (index--)
            prev = prev->next;
        Node* node = new Node(val);
        node->next = prev->next;
        prev->next = node;
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size)
            return;
        Node* prev = head;
        while (index--)
            prev = prev->next;
        Node* temp = prev->next;
        prev->next = temp->next;
        delete temp;
        size--;
    }
};
  • time: O(1) for addAtHead, O(n) for addAtTail, O(k) to reach index k in the rest
  • space: O(n) - one node per element, plus the sentinel
quantinium © 2026