C++ 数组模拟链表：高效实现插入和查询操作

#include\u003cbits\u002Fstdc++.h\u003e using namespace std;

struct ListNode { int value; int next; };

int main() { int n, q; cin >> n >> q; ListNode nodes[n+q+1]; for (int i = 1; i <= n; i++) { cin >> nodes[i].value; nodes[i].next = i + 1; } nodes[n].next = 0; int head = 1; int newNodeIndex = n+1; for (int i = 0; i <q; i++) { int op; cin >> op; if (op == 1) { int k, val; cin >> k >> val; nodes[newNodeIndex].value = val; nodes[newNodeIndex].next = nodes[k].next; nodes[k].next = newNodeIndex; newNodeIndex++; } else if (op == 2) { int k; cin >> k; int cur = head; for (int j = 1; j < k; j++) cur = nodes[cur].next; cout << nodes[cur].value << '\n'; } } return 0; }