实现链表的基本功能
链表的特点就不赘述了，这类的文章特别多，这里以简单的方式手动实现链表的各种操作。
结点结构
链表中的每个结点，包括一个结点值val和指向下一个结点的指针next。
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
实现功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
设计
维护一个链表元素个数size。
所有元素结点index的范围是[0…size-1]，第一个结点的index是0，第二个是1，以此类推。
获取前置结点
因为单链表不能反向遍历，而且插入，删除操作都要对目标结点的前一个结点进行操作，所以特地编写一个获取目标序号之前结点的方法：
如果index=0，就返回头结点；如果index=1，就返回第一个结点；以此类推。
ListNode* findBefore(int index) {
ListNode* p = head;
for (int i = 0; p != nullptr && i < index; i++) {
p = p->next;
}
return p;
}
获取第index个结点的值
借助于前面写的findBefore方法，可以不用另外写一个for循环了。
index超出范围的话，返回-1
int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
return findBefore(index)->next->val;
}
头插
在链表最前面插入新节点，值val，这个结点在head和第一个结点之间。
void addAtHead(int val) {
ListNode* node = new ListNode(val);
node->next = head->next;
head->next = node;
size++;
if (size == 1) {
tail = node;
}
}
尾插
在链表尾部插入新结点，值val。
因为尾插是比较常用的操作，如果每次尾插都遍历链表查找尾结点，性能会比较差，所以这里维护了一个尾结点指针tail。
尾插、删除最后一个结点、空表重复头插都会导致尾结点产生变化，具体维护方式在对应方法里。
void addAtTail(int val) {
ListNode* node = new ListNode(val);
tail->next = node;
tail = node;
size++;
}
在指定index位置插入新结点
在链表中的第 index 个节点之前添加值为 val 的节点，插入的合法范围：index<=size。
如果index<=0则执行头插，index=size则执行尾插。
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index <= 0) {
addAtHead(val);
}
else if (index == size) {
addAtTail(val);
}
else {
ListNode* before = findBefore(index);
ListNode* node = new ListNode(val);
node->next = before->next;
before->next = node;
size++;
}
}
删除指定index位置的结点
index范围[0…size-1]
void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
ListNode* before = findBefore(index);
if (index == size - 1) {
tail = before;
}
ListNode* delNode = before->next;
before->next = delNode->next;
size--;
}
打印链表
每个结点之间用空格分隔。
void printList() {
ListNode* p = head->next;
while (p != nullptr) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
完整代码
用一个链表类实现链表的初始化和各种功能。
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class MyLinkedList {
private:
ListNode* head;
ListNode* tail;
int size;
public:
MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = head;
}
int getSize() {
return size;
}
ListNode* findBefore(int index) {
ListNode* p = head;
for (int i = 0; p != nullptr && i < index; i++) {
p = p->next;
}
return p;
}
int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
return findBefore(index)->next->val;
}
void addAtHead(int val) {
ListNode* node = new ListNode(val);
node->next = head->next;
head->next = node;
size++;
if (size == 1) {
tail = node;
}
}
void addAtTail(int val) {
ListNode* node = new ListNode(val);
tail->next = node;
tail = node;
size++;
}
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index <= 0) {
addAtHead(val);
}
else if (index == size) {
addAtTail(val);
}
else {
ListNode* before = findBefore(index);
ListNode* node = new ListNode(val);
node->next = before->next;
before->next = node;
size++;
}
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
ListNode* before = findBefore(index);
if (index == size - 1) {
tail = before;
}
ListNode* delNode = before->next;
before->next = delNode->next;
size--;
}
void printList() {
ListNode* p = head->next;
while (p != nullptr) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
};
int main() {
MyLinkedList ml;
ml.addAtHead(1);
ml.addAtTail(3);
ml.printList();
ml.deleteAtIndex(0);
ml.printList();
cout << ml.get(0) << endl;
}
|