题目

力扣题目

设计并实现一个链表，支持以下操作：

  • get(index)：获取下标为 index 的节点值，下标无效时返回 -1；
  • addAtHead(val)：在链表头部插入节点；
  • addAtTail(val)：在链表尾部插入节点；
  • addAtIndex(index, val)：在下标 index 对应节点之前插入；当 index == size 时追加到尾部，index > size 时不插入；
  • deleteAtIndex(index)：下标有效时删除对应节点。

本题不能直接使用语言内置的链表容器。

示例：

Text
操作：
MyLinkedList()
addAtHead(1)
addAtTail(3)
addAtIndex(1, 2)
get(1)
deleteAtIndex(1)
get(1)

链表变化：
[] → [1] → [1,3] → [1,2,3] → [1,3]

返回结果：
get(1) 第一次返回 2，第二次返回 3

提示：

  • 0 <= index, val <= 1000
  • 所有接口的调用次数不超过 2000

考察内容

  • 单链表节点结构
  • 虚拟头节点与前驱节点
  • 按下标遍历、插入和删除
  • 链表长度维护
  • 动态内存的申请与释放
  • 数据结构接口的边界定义

解题思路

数据结构

使用单链表实现，每个节点包含：

  • val：当前节点保存的值；
  • next：指向下一个节点。

类中额外维护：

  • dummy_：不属于真实数据的虚拟头节点；
  • size_：真实节点数量。

真实链表始终从 dummy_.next 开始。虚拟头节点使“在下标 0 插入”和“删除下标 0”不再需要特殊修改头指针。

找到目标节点与前驱节点

get(index) 需要找到下标为 index 的真实节点，因此从 dummy_.next 开始移动 index 次。

插入和删除需要修改目标位置前一个节点的 next，所以从 dummy_ 开始移动 index 次：

Text
pre → 原 index 节点

插入时改为：

Text
pre → newNode → 原 index 节点

删除时改为：

Text
pre ─────────→ index 后面的节点

各接口逻辑

get(index)

先验证 0 <= index < size_，再从首个真实节点向后移动。

addAtIndex(index, val)

  • index < 0：按头部插入处理，归一化为 0；
  • index > size_：位置越过链表尾部，不执行插入；
  • index == size_：前驱恰好是当前尾节点，插入后成为新尾节点；
  • 其他情况：在原下标 index 节点前插入。

完成插入后执行 ++size_。

deleteAtIndex(index)

只有 0 <= index < size_ 时才删除。找到目标节点的前驱，将其绕过后释放目标节点，最后执行 --size_。

⤢ 打开

复杂度

当前实现没有额外维护尾指针：

操作时间复杂度说明
get(index)O(index)O(index)遍历到目标节点
addAtHeadO(1)O(1)在虚拟头节点后插入
addAtTailO(n)O(n)遍历到链表尾部
addAtIndexO(index)O(index)遍历到目标前驱
deleteAtIndexO(index)O(index)遍历到目标前驱

额外空间复杂度为 O(1)O(1)，不计链表自身存储节点所需空间。

代码演示

C++
class MyLinkedList {
private:
    struct ListNode {
        int val;
        ListNode* next;

        explicit ListNode(int value = 0, ListNode* next_node = nullptr)
            : val(value), next(next_node) {}
    };

public:
    MyLinkedList() : dummy_(0), size_(0) {}

    ~MyLinkedList() {
        ListNode* cur = dummy_.next;
        while (cur != nullptr) {
            ListNode* next = cur->next;
            delete cur;
            cur = next;
        }
    }

    MyLinkedList(const MyLinkedList&) = delete;
    MyLinkedList& operator=(const MyLinkedList&) = delete;

    int get(int index) const {
        if (index < 0 || index >= size_) {
            return -1;
        }

        const ListNode* cur = dummy_.next;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        return cur->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 = 0;
        }
        if (index > size_) {
            return;
        }

        ListNode* prev = &dummy_;
        for (int i = 0; i < index; ++i) {
            prev = prev->next;
        }

        prev->next = new ListNode(val, prev->next);
        ++size_;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size_) {
            return;
        }

        ListNode* prev = &dummy_;
        for (int i = 0; i < index; ++i) {
            prev = prev->next;
        }

        ListNode* deleted = prev->next;
        prev->next = deleted->next;
        delete deleted;
        --size_;
    }

private:
    ListNode dummy_;
    int size_;
};

易错点

  • 混淆目标节点和前驱节点：插入、删除要找到下标 index 的前驱，因此从 dummy_ 开始移动 index 次。
  • 拒绝 index == size_ 的插入：该情况表示追加到尾部，是合法操作；只有 index > size_ 才不插入。
  • 删除后忘记减少长度：成功插入和删除后必须分别更新 size_。
  • 无效删除仍减少长度：边界检查失败时必须直接返回。
  • 覆盖丢失后续链表：创建新节点时，应先让它指向原目标节点，再让前驱指向新节点。
  • 释放节点后继续访问：删除前保存连接关系，完成重连后再 delete。
  • 动态分配虚拟头节点却不释放：这里直接将 dummy_ 作为成员对象，生命周期由类自动管理。
  • 添加析构函数后保留默认浅拷贝：浅拷贝会让两个对象持有相同节点，产生重复释放；示例显式禁用了拷贝。

总结

设计链表的核心是统一位置语义：真实节点从下标 0 开始，size_ 表示可访问节点数量，而插入、删除通过虚拟头节点寻找前驱。只要明确“从哪里出发、移动几次、修改哪一条 next”，各接口就能使用一致的逻辑实现。

相关题目

    1. 移除链表元素
    1. 反转链表
    1. 删除链表的倒数第 N 个结点
    1. 设计跳表