09 链表（Linked List）

#include <iostream>
using namespace std;

struct Node {                // 链表结点：数据 + 指向下一个的指针
    int data;                // 数据域
    Node *next;              // 指针域
    Node(int d, Node *n = nullptr) : data(d), next(n) {}   // 构造函数
};

// 在链表头部插入新结点（头插法）
Node *insertHead(Node *head, int val) {
    return new Node(val, head);   // 新结点指向原头，自己成为新头
}

// 打印链表：从头沿 next 遍历
void printList(Node *head) {
    while (head) {
        cout << head->data << " ";
        head = head->next;        // 移到下一个结点
    }
    cout << endl;
}

// 释放整条链表内存（防止内存泄漏）
void freeList(Node *head) {
    while (head) {
        Node *t = head;           // 先记住当前结点
        head = head->next;        // 再后移
        delete t;                 // 删除当前结点
    }
}

int main() {
    Node *head = nullptr;         // 空链表
    head = insertHead(head, 3);
    head = insertHead(head, 2);
    head = insertHead(head, 1);
    printList(head);   // 1 2 3（头插法，最后插入的在最前）
    freeList(head);
    return 0;
}

// 数组模拟单链表：用两个数组分别存"值"和"后继下标"
#include <iostream>
using namespace std;
const int N = 100005;
int dataArr[N], nextIdx[N];   // dataArr 存节点值，nextIdx 存下一个节点的下标
int head = -1, cnt = 0;       // head=-1 表示空链表，cnt 是节点池指针

// 头插：把值为 x 的新节点插到链表头部
void insertHead(int x) {
    dataArr[cnt] = x;         // 在节点池中登记值
    nextIdx[cnt] = head;      // 新节点指向旧头
    head = cnt;               // 新节点成为头
    cnt++;                    // 池指针后移
}

void printList() {
    for (int p = head; p != -1; p = nextIdx[p]) {  // 沿 nextIdx 链走
        cout << dataArr[p] << " ";
    }
    cout << endl;
}

int main() {
    insertHead(3);
    insertHead(2);
    insertHead(1);
    printList();   // 1 2 3
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100005;
int nxt[N];        // 只记录后继下标
// 约瑟夫环的链表实现：节点 i 指向 i+1，最后一个指向 1 成环
int main() {
    int n, m;
    cin >> n >> m;              // 约瑟夫环：n 人，数到 m 出列
    for (int i = 1; i < n; i++) nxt[i] = i + 1;
    nxt[n] = 1;                 // 尾指向头，形成循环链表
    int p = n;                  // 从 n 开始，使第一次报数从 1 起
    for (int k = 1; k <= n; k++) {          // 依次删除 n 个人
        for (int i = 1; i < m; i++) p = nxt[p];   // 走 m-1 步找到出列者前驱
        cout << nxt[p] << " ";              // 出列者（p 的后继）
        nxt[p] = nxt[nxt[p]];               // 链式删除：越过出列者
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<int> L;               // STL 双向链表
    L.push_back(1);            // 尾部插入
    L.push_back(3);
    L.push_front(0);           // 头部插入
    // 在中间插入：找到值 1 的节点，在其后插入 2
    for (auto it = L.begin(); it != L.end(); ++it) {
        if (*it == 1) {
            L.insert(it, 2);   // 在迭代器 it 之前插入（即 1 之后）
            break;
        }
    }
    for (int x : L) cout << x << " ";
    cout << endl;   // 0 2 1 3
    return 0;
}