题目描述

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

解题思路

1. 数据结构设计

• 使用单向链表节点结构：包含数据域val和指针域next

• 维护链表的虚拟头节点dummyHead，简化边界处理

• 维护链表长度size，提高索引有效性检查效率

2. 关键设计要点

• 虚拟头节点：避免头节点插入/删除的特殊处理

• 长度维护：实时更新链表长度，快速进行边界检查

• 统一的插入逻辑：所有插入操作都可以转化为在指定位置插入

3. 操作实现策略

获取节点 (get)：

• 检查索引有效性

• 从头节点开始遍历到目标位置

头部插入 (addAtHead)：

• 等价于在索引0位置插入

尾部插入 (addAtTail)：

• 等价于在索引size位置插入

指定位置插入 (addAtIndex)：

• 找到插入位置的前驱节点

• 创建新节点并调整指针关系

删除节点 (deleteAtIndex)：

• 找到删除位置的前驱节点

• 调整指针关系并释放内存

复杂度分析

时间复杂度分析

• get(index): O(index) - 需要遍历到目标位置

• addAtHead(val): O(1) - 直接在头部插入

• addAtTail(val): O(size) - 需要遍历到尾部

• addAtIndex(index, val): O(index) - 需要遍历到插入位置

• deleteAtIndex(index): O(index) - 需要遍历到删除位置

空间复杂度分析

• 空间复杂度：O(n)，其中n是链表中的节点数量

• 额外空间：O(1)，只使用了常数级别的额外空间

代码实现

class MyLinkedList {
private:
    // 链表节点结构
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x): val(x), next(nullptr) {}
    };
​
    // 虚拟头节点，简化边界处理
    ListNode *dummyHead; 
​
     // 链表长度
    int size;
public:
    // 初始化链表
    MyLinkedList() {
        dummyHead = new ListNode(0);
        size = 0;
    }
​
    // 析构函数，释放所有节点的内存
    ~MyLinkedList() {
        ListNode *curr = dummyHead;
        while (curr != nullptr) {
            ListNode *temp = curr;
            curr = curr->next;
            delete temp;
        }
    }   
​
    // 获取链表种第index个节点的值，如果索引无效，则返回-1
    int get(int index) {
        // 检查索引的有效性
        if (index < 0 || index >= size) {
            return -1;
        }
​
        ListNode *curr = dummyHead->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
​
        return curr->val;
    }
    
    // 在链表的第一个元素之前添加一个值为val的节点 
    void addAtHead(int val) {   
        addAtIndex(0 , val);
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    // 在链表中得第index个节点之前添加值为val的节点
    void addAtIndex(int index, int val) {
        // 索引检查：允许在末尾插入(index == size)
        if (index < 0 || index > size) {
            return;
        }
​
        // 找到插入位置的前驱节点
        ListNode *prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
​
        // 创建新节点并插入
        ListNode *newNode = new ListNode(val);
        newNode->next = prev->next;
        prev->next = newNode;
​
        //更新链表长度
        size++;
    }
    
    // 删除链表中的第index个节点
    void deleteAtIndex(int index) {
        // 检查索引有效性
        if (index < 0 || index >= size) {
            return;
        }
​
        // 找到删除位置的前驱节点
        ListNode *prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
​
        // 删除节点
        ListNode *nodeToDelete = prev->next;
        prev->next = nodeToDelete->next;
        delete nodeToDelete;
​
        //更新链表长度
        size--;
    }
};