LeetCode 707：设计链表

LeetCode 707 要求设计并实现一个支持多种操作（获取、添加、删除）的单链表类。核心在于定义包含值和指针的节点结构，维护头指针与链表大小。实现细节包括索引越界检查、头尾插入的顺序控制、中间节点遍历修改指针，以及析构时的内存释放。代码示例展示了标准 C++ 实现方式，并通过哑节点技巧优化了插入与删除逻辑，确保边界情况下的正确性与内存安全。

芝士奶盖发布于 2026/3/15更新于 2026/4/185 浏览

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入: ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 输出: [null, null, null, null, 2, null, 3] 解释:

MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3

思路分析

1. 总体思路

先在类里面创建结构体，制造链表所包含的要求，再分析每一个函数所要求的，最后析构即可。

2. 实现细节

1. 结构体设置

设置结构体的时候，要设置一个有参构造，以应对新的 ListNode 的插入，同时要在结构体外部设置一个头指针 head 和用来表示链表大小的 size。

2. get 部分

首先要注意的是，判断 index 是否合法的条件是 <0 和 >=size，这里的 >=size 是因为我们的链表是从 0 开始，末尾的那个链表部分的序号是 size-1，接下来就是用 cur 指针遍历了。

3. addAtHead 部分

这里要注意的是这两行代码不能颠倒顺序，因为颠倒后 newNode->next 指向不了你所需的先前的 head。

newNode->next = head;
head = newNode;

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

class MyLinkedList { private: struct ListNode { int val; ListNode* next; ListNode(int x):val(x),next(nullptr){} }; ListNode* head; int size; public: MyLinkedList() { head=nullptr; size=0; } int get(int index) { if(index<0||index>=size) return -1; ListNode* cur=head; for(int i=0;i<index;i++) { cur=cur->next; } return cur->val; } void addAtHead(int val) { ListNode* newNode= new ListNode(val); newNode->next=head; head=newNode; size++; } void addAtTail(int val) { ListNode* newNode=new ListNode(val); if(head==nullptr) { head=newNode; } else { ListNode* cur=head; while(cur->next!=nullptr) { cur=cur->next; } cur->next=newNode; } size++; } void addAtIndex(int index, int val) { if(index<0||index>size) return; if(index==0) { addAtHead(val); return; } if(index==size) { addAtTail(val); return; } ListNode* cur=head; for(int i=0;i<index-1;i++) { cur=cur->next; } ListNode* newNode=new ListNode(val); newNode->next=cur->next; cur->next=newNode; size++; } void deleteAtIndex(int index) { if(index<0||index>=size) return; if(index==0) { ListNode* temp=head; head=head->next; delete temp; } else { ListNode* cur=head; for(int i=0;i<index-1;i++) { cur=cur->next; } ListNode* temp=cur->next; cur->next=cur->next->next; delete temp; } size--; } ~MyLinkedList() { ListNode* cur=head; while(cur!=nullptr) { ListNode* temp=cur; cur=cur->next; delete temp; } } };

LeetCode 707：设计链表

题目描述

思路分析

1. 总体思路

2. 实现细节

1. 结构体设置

2. get 部分

3. addAtHead 部分

更多推荐文章

相关免费在线工具

4. addAtTail 部分

5. addAtIndex 部分

6. deleteAtIndex 部分

7. ~MyLinkedList 部分

代码实现

LeetCode 707：设计链表

题目描述

思路分析

1. 总体思路

2. 实现细节

1. 结构体设置

2. get 部分

3. addAtHead 部分

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

4. addAtTail 部分

5. addAtIndex 部分

6. deleteAtIndex 部分

7. ~MyLinkedList 部分

代码实现