题目链接:https://leetcode.cn/problems/design-linked-list/
C++代码如下:
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) {
// 如果索引无效,则返回-1
if (index < 0 || index >= size) return -1;
// 获取链表中第index个节点的值
auto cur = head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
// 在链表的第一个元素之前添加一个值为val的节点,插入后,新节点将成为链表的第一个节点
auto tmp = new ListNode(val);
tmp->next = head;
head = tmp;
size++;
}
void addAtTail(int val) {
// 如果链表中没有节点,则插入的新节点将成为链表的第一个节点
if (head == nullptr) {
head = new ListNode(val);
size++;
return;
}
// 如果链表中有节点,则将值为val的节点追加到链表的末尾
auto cur = head;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = new ListNode(val);
size++;
}
void addAtIndex(int index, int val) {
// 如果index大于链表长度,则直接返回
if (index > size) return;
// 如果index小于等于0,则在头部插入值为val的节点
if (index <= 0) {
addAtHead(val);
return;
}
// 如果index等于链表长度,则将值为val的节点追加到链表的末尾
if (index == size) {
addAtTail(val);
return;
}
// 在链表的第index个节点之前添加值为val的节点
auto cur = head;
for (int i = 0; i < index - 1; i++) {
cur = cur->next;
}
auto tmp = new ListNode(val);
tmp->next = cur->next;
cur->next = tmp;
size++;
}
void deleteAtIndex(int index) {
// 如果索引无效,则直接返回
if (index < 0 || index >= size) return;
// 删除链表的第一个节点
if (index == 0) {
head = head->next;
size--;
return;
}
// 删除链表的第index个节点
auto cur = head;
for (int i = 0; i < index - 1; i++) {
cur = cur->next;
}
cur->next = cur->next->next;
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);
*/
注:上面代码侧重于算法实现,没有进行内存管理,这对C/C++选手来说,实属缺憾。