AcWing 826. 单链表 C++
原题链接
简单
作者:
张立斌
,
2019-10-25 19:00:07
,
所有人可见
,
阅读 1039
main函数
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int m, k, x;
scanf("%d", &m);
StaticSList sList;
for (int i = 0; i < m; ++i) {
char oper[2];
scanf("%2s", oper);
switch (oper[0]) {
case 'H':
scanf("%d", &x);
sList.pushFront(x);
break;
case 'D':
scanf("%d", &k);
sList.eraseAfter(k - 1);
break;
case 'I':
scanf("%d%d", &k, &x);
sList.insertAfter(k - 1, x);
break;
default:;
}
}
for (int i = sList.beginIndex(); i != sList.endIndex(); i = sList.nextIndex(i)) {
int value = sList[i];
printf("%d ", value);
}
puts("");
return 0;
}
静态链表
class StaticSList {
struct ListNode {
int value;
int next;
};
public:
explicit StaticSList(int capacity = 64) : head(-1) { nodeVec.reserve(capacity); }
void pushFront(int value) {
nodeVec.push_back({value, head});
head = nodeVecSize() - 1;
}
void insertAfter(int index, int value) {
if (index == -1) {
pushFront(value);
} else {
nodeVec.push_back({value, nodeVec[index].next});
nodeVec[index].next = nodeVecSize() - 1;
}
}
void popFront() { head = nodeVec[head].next; }
void eraseAfter(int index) {
if (index == -1) {
popFront();
} else {
nodeVec[index].next = nodeVec[nodeVec[index].next].next;
}
}
inline int beginIndex() const { return head; }
inline int endIndex() const { return -1; }
inline int nextIndex(int index) const { return nodeVec[index].next; }
inline int &operator[](int index) { return nodeVec[index].value; }
private:
inline int nodeVecSize() const { return nodeVec.size(); }
int head;
vector<ListNode> nodeVec;
};