设计链表完整实现【单链表】【双链表】
·
设计链表完整实现详解
目录
概述
设计链表是数据结构学习中的经典题目,它要求我们实现一个完整的链表类,包含增删改查等基本操作。这道题不仅考察了链表的基本操作,还涉及虚拟头节点、单链表与双链表的选择等核心概念。通过这道题,我们可以深入理解链表的本质和实现技巧。
题目分析
题目要求
实现 MyLinkedList 类,包含以下五个核心方法:
- get(index) - 获取第index个节点的值
- addAtHead(val) - 在链表头部插入节点
- addAtTail(val) - 在链表尾部插入节点
- addAtIndex(index, val) - 在指定位置插入节点
- deleteAtIndex(index) - 删除指定位置的节点
关键挑战
- 边界条件处理:索引越界、空链表等
- 头节点特殊处理:插入/删除头节点需要特殊逻辑
- 性能优化:选择合适的链表类型和遍历策略
- 内存管理:正确释放被删除节点的内存
单链表实现
核心思想
使用虚拟头节点统一所有操作,避免头节点的特殊处理。
数据结构设计
struct LinkedNode {
int val; // 节点值
LinkedNode* next; // 指向下一个节点的指针
LinkedNode(int val):val(val), next(nullptr){} // 构造函数
};
完整实现(C++)
class MyLinkedList {
public:
// 定义链表节点结构体
struct LinkedNode {
int val; // 节点存储的值
LinkedNode* next; // 指向下一个节点的指针
LinkedNode(int val):val(val), next(nullptr){} // 构造函数
};
// 初始化链表
MyLinkedList() {
_dummyHead = new LinkedNode(0); // 创建虚拟头节点,值为0
_size = 0; // 初始化链表大小为0
}
// 获取第index个节点的值
int get(int index) {
// 边界检查:索引无效返回-1
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead->next; // 从第一个真实节点开始
while(index--) { // 移动到目标位置
cur = cur->next;
}
return cur->val; // 返回节点值
}
// 在链表头部插入节点
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val); // 创建新节点
newNode->next = _dummyHead->next; // 新节点指向原头节点
_dummyHead->next = newNode; // 虚拟头节点指向新节点
_size++; // 链表大小加1
}
// 在链表尾部插入节点
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val); // 创建新节点
LinkedNode* cur = _dummyHead; // 从虚拟头节点开始
while(cur->next != nullptr) { // 找到最后一个节点
cur = cur->next;
}
cur->next = newNode; // 在尾部插入新节点
_size++; // 链表大小加1
}
// 在指定位置插入节点
void addAtIndex(int index, int val) {
// 边界检查
if(index > _size) return; // 索引超出范围
if(index < 0) index = 0; // 负数索引视为0
LinkedNode* newNode = new LinkedNode(val); // 创建新节点
LinkedNode* cur = _dummyHead; // 从虚拟头节点开始
while(index--) { // 移动到插入位置的前一个节点
cur = cur->next;
}
newNode->next = cur->next; // 新节点指向下一个节点
cur->next = newNode; // 前一个节点指向新节点
_size++; // 链表大小加1
}
// 删除指定位置的节点
void deleteAtIndex(int index) {
// 边界检查
if (index >= _size || index < 0) {
return;
}
LinkedNode* cur = _dummyHead; // 从虚拟头节点开始
while(index--) { // 移动到删除位置的前一个节点
cur = cur->next;
}
LinkedNode* tmp = cur->next; // 保存要删除的节点
cur->next = cur->next->next; // 跳过要删除的节点
delete tmp; // 释放内存
tmp = nullptr; // 避免野指针
_size--; // 链表大小减1
}
// 打印链表(调试用)
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size; // 链表大小
LinkedNode* _dummyHead; // 虚拟头节点
};
图示说明
虚拟头节点的作用:
原始链表:1 -> 2 -> 3 -> null
添加虚拟头节点:dummy -> 1 -> 2 -> 3 -> null
↑
虚拟头节点
插入操作示例:
在头部插入0:
dummy -> 0 -> 1 -> 2 -> 3 -> null
在位置1插入5:
dummy -> 0 -> 5 -> 1 -> 2 -> 3 -> null
双链表实现
核心思想
使用循环虚拟节点(哨兵节点),支持双向遍历,提高查找效率。
数据结构设计
struct DList {
int elem; // 节点值
DList *next; // 指向下一个节点
DList *prev; // 指向上一个节点
DList(int elem) : elem(elem), next(nullptr), prev(nullptr) {};
};
完整实现(C++)
class MyLinkedList {
public:
// 定义双向链表节点结构体
struct DList {
int elem; // 节点存储的元素
DList *next; // 指向下一个节点的指针
DList *prev; // 指向上一个节点的指针
DList(int elem) : elem(elem), next(nullptr), prev(nullptr) {}; // 构造函数
};
// 构造函数,初始化链表
MyLinkedList() {
sentinelNode = new DList(0); // 创建哨兵节点
sentinelNode->next = sentinelNode; // 哨兵节点指向自身,形成循环
sentinelNode->prev = sentinelNode; // 哨兵节点指向自身,形成循环
size = 0; // 初始化链表大小为0
}
// 获取第index个节点的值
int get(int index) {
if (index > (size - 1) || index < 0) { // 边界检查
return -1;
}
int mid = size >> 1; // 计算链表中部位置
DList *curNode = sentinelNode; // 从哨兵节点开始
if (index < mid) { // 从前半部分查找
for (int i = 0; i < index + 1; i++) {
curNode = curNode->next;
}
} else { // 从后半部分查找
for (int i = 0; i < size - index; i++) {
curNode = curNode->prev;
}
}
return curNode->elem; // 返回节点值
}
// 在链表头部添加节点
void addAtHead(int val) {
DList *newNode = new DList(val); // 创建新节点
DList *next = sentinelNode->next; // 获取当前头节点
newNode->prev = sentinelNode; // 新节点的前驱指向哨兵节点
newNode->next = next; // 新节点的后继指向原头节点
sentinelNode->next = newNode; // 哨兵节点的后继指向新节点
next->prev = newNode; // 原头节点的前驱指向新节点
size++; // 链表大小加1
}
// 在链表尾部添加节点
void addAtTail(int val) {
DList *newNode = new DList(val); // 创建新节点
DList *prev = sentinelNode->prev; // 获取当前尾节点
newNode->next = sentinelNode; // 新节点的后继指向哨兵节点
newNode->prev = prev; // 新节点的前驱指向原尾节点
sentinelNode->prev = newNode; // 哨兵节点的前驱指向新节点
prev->next = newNode; // 原尾节点的后继指向新节点
size++; // 链表大小加1
}
// 在指定位置插入节点
void addAtIndex(int index, int val) {
if (index > size) return; // 边界检查
if (index <= 0) { // 在头部插入
addAtHead(val);
return;
}
int mid = size >> 1; // 计算链表中部位置
DList *curNode = sentinelNode; // 从哨兵节点开始
if (index < mid) { // 从前半部分查找插入位置
for (int i = 0; i < index; i++) {
curNode = curNode->next;
}
DList *temp = curNode->next; // 目标位置的节点
DList *newNode = new DList(val); // 创建新节点
curNode->next = newNode; // 插入新节点
temp->prev = newNode;
newNode->next = temp;
newNode->prev = curNode;
} else { // 从后半部分查找插入位置
for (int i = 0; i < size - index; i++) {
curNode = curNode->prev;
}
DList *temp = curNode->prev; // 目标位置的节点
DList *newNode = new DList(val); // 创建新节点
curNode->prev = newNode; // 插入新节点
temp->next = newNode;
newNode->prev = temp;
newNode->next = curNode;
}
size++; // 链表大小加1
}
// 删除指定位置的节点
void deleteAtIndex(int index) {
if (index > (size - 1) || index < 0) { // 边界检查
return;
}
int mid = size >> 1; // 计算链表中部位置
DList *curNode = sentinelNode; // 从哨兵节点开始
if (index < mid) { // 从前半部分查找删除位置
for (int i = 0; i < index; i++) {
curNode = curNode->next;
}
DList *next = curNode->next->next; // 目标位置的下一个节点
curNode->next = next; // 删除目标节点
next->prev = curNode;
} else { // 从后半部分查找删除位置
for (int i = 0; i < size - index - 1; i++) {
curNode = curNode->prev;
}
DList *prev = curNode->prev->prev; // 目标位置的上一个节点
curNode->prev = prev; // 删除目标节点
prev->next = curNode;
}
size--; // 链表大小减1
}
private:
int size; // 链表大小
DList *sentinelNode; // 哨兵节点
};
图示说明
循环双链表结构:
哨兵节点 <-> 节点1 <-> 节点2 <-> 节点3 <-> 哨兵节点
↑ ↑
└─────────────── 循环连接 ──────────────────┘
双向遍历优化:
查找第2个节点(总共5个节点):
- 从前向后:需要2步
- 从后向前:需要2步
选择更短的路径
虚拟头节点的必要性
问题分析
不使用虚拟头节点的问题:
// 需要特殊处理头节点
if (head == nullptr) {
head = new ListNode(val);
} else {
// 插入逻辑
}
使用虚拟头节点的优势:
// 统一处理所有节点
dummy->next = newNode;
newNode->next = cur->next;
cur->next = newNode;
核心作用
- 统一操作逻辑:所有节点都可以用相同的插入/删除逻辑
- 简化边界条件:不需要特殊处理头节点为空的情况
- 提高代码健壮性:避免头节点相关的边界错误
- 增强可读性:代码逻辑更加清晰
图示对比
不使用虚拟头节点:
原始链表:1 -> 2 -> 3
插入头节点需要特殊处理:
新节点 -> 1 -> 2 -> 3
使用虚拟头节点:
虚拟头节点 -> 1 -> 2 -> 3
插入操作统一:
虚拟头节点 -> 新节点 -> 1 -> 2 -> 3
单链表与双链表的对比
性能对比
| 操作 | 单链表 | 双链表 |
|---|---|---|
| 查找 | O(n) | O(n/2) |
| 插入 | O(n) | O(n/2) |
| 删除 | O(n) | O(n/2) |
| 空间复杂度 | O(n) | O(n) |
| 实现复杂度 | 简单 | 复杂 |
适用场景
单链表适合:
- 简单的线性操作
- 内存使用要求严格
- 实现简单性要求高
双链表适合:
- 需要频繁的随机访问
- 需要双向遍历
- 性能要求较高
选择建议
- 一般情况:选择单链表,实现简单
- 性能要求高:选择双链表
- 内存受限:选择单链表
- 需要双向操作:选择双链表
C++实现详解
内存管理要点
// 正确的内存释放
void deleteAtIndex(int index) {
// ... 查找逻辑 ...
LinkedNode* tmp = cur->next; // 保存要删除的节点
cur->next = cur->next->next; // 跳过要删除的节点
delete tmp; // 释放内存
tmp = nullptr; // 避免野指针
}
边界条件处理
// 完整的边界检查
int get(int index) {
if (index > (_size - 1) || index < 0) { // 检查索引范围
return -1;
}
// ... 查找逻辑 ...
}
Python实现详解
单链表实现(Python)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val # 节点值
self.next = next # 指向下一个节点的引用
class MyLinkedList:
def __init__(self):
self.dummy_head = ListNode() # 创建虚拟头节点
self.size = 0 # 初始化链表大小
def get(self, index: int) -> int:
# 边界检查
if index < 0 or index >= self.size:
return -1
current = self.dummy_head.next # 从第一个真实节点开始
for i in range(index): # 移动到目标位置
current = current.next
return current.val # 返回节点值
def addAtHead(self, val: int) -> None:
# 在虚拟头节点后插入新节点
self.dummy_head.next = ListNode(val, self.dummy_head.next)
self.size += 1 # 链表大小加1
def addAtTail(self, val: int) -> None:
current = self.dummy_head # 从虚拟头节点开始
while current.next: # 找到最后一个节点
current = current.next
current.next = ListNode(val) # 在尾部插入新节点
self.size += 1 # 链表大小加1
def addAtIndex(self, index: int, val: int) -> None:
# 边界检查
if index < 0 or index > self.size:
return
current = self.dummy_head # 从虚拟头节点开始
for i in range(index): # 移动到插入位置的前一个节点
current = current.next
# 插入新节点
current.next = ListNode(val, current.next)
self.size += 1 # 链表大小加1
def deleteAtIndex(self, index: int) -> None:
# 边界检查
if index < 0 or index >= self.size:
return
current = self.dummy_head # 从虚拟头节点开始
for i in range(index): # 移动到删除位置的前一个节点
current = current.next
# 删除节点(Python自动垃圾回收)
current.next = current.next.next
self.size -= 1 # 链表大小减1
双链表实现(Python)
class ListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val # 节点值
self.prev = prev # 指向上一个节点的引用
self.next = next # 指向下一个节点的引用
class MyLinkedList:
def __init__(self):
self.head = None # 头节点
self.tail = None # 尾节点
self.size = 0 # 链表大小
def get(self, index: int) -> int:
# 边界检查
if index < 0 or index >= self.size:
return -1
# 根据索引位置选择遍历方向
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index - 1):
current = current.prev
return current.val
def addAtHead(self, val: int) -> None:
new_node = ListNode(val, None, self.head) # 创建新节点
if self.head:
self.head.prev = new_node # 更新原头节点的前驱
else:
self.tail = new_node # 如果链表为空,新节点也是尾节点
self.head = new_node # 更新头节点
self.size += 1 # 链表大小加1
def addAtTail(self, val: int) -> None:
new_node = ListNode(val, self.tail, None) # 创建新节点
if self.tail:
self.tail.next = new_node # 更新原尾节点的后继
else:
self.head = new_node # 如果链表为空,新节点也是头节点
self.tail = new_node # 更新尾节点
self.size += 1 # 链表大小加1
def addAtIndex(self, index: int, val: int) -> None:
# 边界检查
if index < 0 or index > self.size:
return
if index == 0:
self.addAtHead(val) # 在头部插入
elif index == self.size:
self.addAtTail(val) # 在尾部插入
else:
# 找到插入位置的前一个节点
if index < self.size // 2:
current = self.head
for i in range(index - 1):
current = current.next
else:
current = self.tail
for i in range(self.size - index):
current = current.prev
# 插入新节点
new_node = ListNode(val, current, current.next)
current.next.prev = new_node
current.next = new_node
self.size += 1
def deleteAtIndex(self, index: int) -> None:
# 边界检查
if index < 0 or index >= self.size:
return
if index == 0:
# 删除头节点
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None
elif index == self.size - 1:
# 删除尾节点
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.head = None
else:
# 删除中间节点
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index - 1):
current = current.prev
# 删除节点
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1 # 链表大小减1
算法技巧总结
1. 虚拟头节点技巧
- 作用:统一操作逻辑,简化边界条件
- 适用场景:需要修改头节点的操作
- 实现要点:记得释放虚拟头节点的内存
2. 双向遍历优化
- 原理:根据索引位置选择更短的遍历路径
- 实现:比较索引与链表长度的一半
- 效果:将平均时间复杂度从O(n)降低到O(n/2)
3. 边界条件处理
- 索引检查:确保索引在有效范围内
- 空链表处理:处理链表为空的情况
- 单节点处理:处理只有一个节点的情况
4. 内存管理
- C++:手动释放内存,避免内存泄漏
- Python/Java:自动垃圾回收,无需手动管理
5. 循环双链表设计
- 哨兵节点:简化边界条件处理
- 循环连接:统一头尾节点的操作
- 双向指针:支持双向遍历
总结
核心要点
- 虚拟头节点是链表操作的核心技巧,能够大大简化代码逻辑
- 双链表通过双向遍历优化,提高查找效率
- 边界条件处理是链表操作的关键,需要仔细考虑各种情况
- 内存管理在不同语言中有不同的处理方式
学习建议
- 掌握虚拟头节点:理解其原理和应用场景
- 熟练链表操作:掌握增删改查的基本操作
- 理解性能优化:学会选择合适的链表类型
- 注意边界条件:养成良好的编程习惯
进阶方向
- 链表排序:归并排序、快速排序在链表上的应用
- 链表检测:环检测、相交检测等高级操作
- 链表反转:部分反转、K个一组反转等
- 链表合并:多链表合并、有序链表合并等
设计链表这道题是链表操作的集大成者,掌握好这道题,就能应对大部分链表相关的问题。通过虚拟头节点、双向遍历等技巧,我们能够写出高效、健壮的链表实现。
代码调试
// 可以写在外面吗? 实测可以
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode() : val(0), next(nullptr) {}
LinkedNode(int val) : val(val), next(nullptr) {}
LinkedNode(int val, LinkedNode* next) : val(val), next(next) {}
};
class MyLinkedList {
public:
// 在单链表内部定义节点结构体
// struct LinkedNode {
// int val;
// LinkedNode* next;
// LinkedNode() : val(0), next(nullptr) {}
// LinkedNode(int x) : val(x), next(nullptr) {}
// LinkedNode(int x, LinkedNode* next) : val(x), next(next) {}
// }; // 能写出去吗?
// 构造函数初始化单向链表
MyLinkedList() {
_dummyHead = new LinkedNode(0); // 虚拟头节点,须分配内存
_size = 0; // 初始化链表大小为0
}
// 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
// index索引位置的值
int get(int index) {
// 关键点:索引是否越界?
if (index > (_size - 1) || index < 0) {
return -1;
}
// LinkedNode* cur = _dummyHead;
// while (index--) {
// cur = cur->next;
// }
// return cur->next->val;
LinkedNode* cur = _dummyHead->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
// 头部插入 (虚拟头节点 ——> 真头节点)
// 目前:(_dummyHead->next==TRUEhead)
// 目标:(newNode ——> TRUEhead)
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val); // 创建新节点
// 原来的头节点是 _dummyHead->next
newNode->next = _dummyHead->next; // 新节点接上原来的头节点
_dummyHead->next = newNode; // 更新虚拟头节点
_size++; // 链表长度+1
}
// 尾部插入 ——> 1.找到尾部位置 2. 插入
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val); // 分配内存, 创建节点
LinkedNode* cur = _dummyHead; // cur从虚拟头节点开始遍历
// 关键问题: 循环不变量和循环条件?cur==最后一个节点时, 执行插入操作!
while (cur->next != nullptr) { // 找到最后一个节点
cur = cur->next;
}
// 此时cur就是单链表最后一个元素了
cur->next = newNode; // 连接新节点
_size++; // 链表大小
}
// 增加一个Index下标位置节点
void addAtIndex(int index, int val) {
// 涉及到index的操作都需要检查边界!
if (index > (_size - 1) || index < 0) {
return; // 什么也不做直接返回
}
LinkedNode* cur = _dummyHead;
LinkedNode* newNode = new LinkedNode(val);
while (index--) {
cur = cur->next;
}
// cur 【index位置 要插入newNode】 cur->next
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
// 删除Index下标位置的节点
void deleteAtIndex(int index) {
if (index > (_size - 1) || index < 0) {
return; // 什么也不做直接返回
}
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp; // 释放被删除节点的内存
tmp = nullptr; // 避免野指针
_size--;
}
// 打印链表用于调试
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
}
private: // _xxx 表示封装为内部变量
LinkedNode* _dummyHead; // 虚拟头节点定义
int _size; // 链表大小
};
int mian() {
}
/**
* 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);
*/
有个用例一直通过不了,想打印检查看看!
一番调试后发现就是边界检查的问题
涉及到索引的问题都要注意边界检查!
// 可以写在外面吗? 实测可以
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode() : val(0), next(nullptr) {}
LinkedNode(int val) : val(val), next(nullptr) {}
// LinkedNode(int val, LinkedNode* next) : val(val), next(next) {}
};
class MyLinkedList {
public:
// 在单链表内部定义节点结构体
// struct LinkedNode {
// int val;
// LinkedNode* next;
// LinkedNode() : val(0), next(nullptr) {}
// LinkedNode(int x) : val(x), next(nullptr) {}
// LinkedNode(int x, LinkedNode* next) : val(x), next(next) {}
// }; // 能写出去吗?
// 构造函数初始化单向链表
MyLinkedList() {
_dummyHead = new LinkedNode(0); // 虚拟头节点,须分配内存
_size = 0; // 初始化链表大小为0
}
// 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
// index索引位置的值
int get(int index) {
// 关键点:索引是否越界?
if (index > (_size - 1) || index < 0) {
return -1;
}
// LinkedNode* cur = _dummyHead;
// while (index--) {
// cur = cur->next;
// }
// return cur->next->val;
LinkedNode* cur = _dummyHead->next;
while (index--) {
cur = cur->next;
}
return cur->val;
// printLinkedList();
}
// 头部插入 (虚拟头节点 ——> 真头节点)
// 目前:(_dummyHead->next==TRUEhead)
// 目标:(newNode ——> TRUEhead)
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val); // 创建新节点
// 原来的头节点是 _dummyHead->next
newNode->next = _dummyHead->next; // 新节点接上原来的头节点
_dummyHead->next = newNode; // 更新虚拟头节点
_size++; // 链表长度+1
// printLinkedList();
}
// 尾部插入 ——> 1.找到尾部位置 2. 插入
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val); // 分配内存, 创建节点
LinkedNode* cur = _dummyHead; // cur从虚拟头节点开始遍历
// 关键问题: 循环不变量和循环条件?cur==最后一个节点时, 执行插入操作!
while (cur->next != nullptr) { // 找到最后一个节点
cur = cur->next;
}
// 此时cur就是单链表最后一个元素了
cur->next = newNode; // 连接新节点
_size++; // 链表大小
// printLinkedList();
}
// 增加一个Index下标位置节点
void addAtIndex(int index, int val) {
// 涉及到index的操作都需要检查边界!
/********************检查出来了!这里逻辑有问题!***********************/
// if (index >= _size || index < 0) {
// printLinkedList();
// return; // 什么也不做直接返回
// }
/********************检查出来了!这里逻辑有问题!***********************/
if (index < 0) addAtHead(val);
if (index > _size) return;
LinkedNode* cur = _dummyHead;
LinkedNode* newNode = new LinkedNode(val);
while (index--) {
cur = cur->next;
}
// cur 【index位置 要插入newNode】 cur->next
newNode->next = cur->next;
cur->next = newNode;
_size++;
// printLinkedList();
}
// 删除Index下标位置的节点
void deleteAtIndex(int index) {
if (index > (_size - 1) || index < 0) {
// printLinkedList();
return; // 什么也不做直接返回
}
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp; // 释放被删除节点的内存
tmp = nullptr; // 避免野指针
_size--;
// printLinkedList();
}
// 打印链表用于调试
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " " ;
cur = cur->next;
}
cout << endl;
}
private: // _xxx 表示封装为内部变量
LinkedNode* _dummyHead; // 虚拟头节点定义
int _size; // 链表大小
};
/**
* 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);
*/
更多推荐

所有评论(0)