#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 42;

    int* p = &x;   // p 保存 x 的地址（p「指向」x）

    cout << x  << "\n";   // 42      —— x 里的数据
    cout << &x << "\n";   // 0x...   —— x 的地址（每次运行可能不同）
    cout << p  << "\n";   // 0x...   —— 和 &x 相同，p 保存的就是这个地址
    cout << *p << "\n";   // 42      —— 解引用：顺着地址找到 x，读出 42

    *p = 100;             // 通过指针修改 x（顺着门牌号去改房间内容）
    cout << x << "\n";    // 100     —— x 真的被改了！

    return 0;
}

int x = 10, y = 20;

// ---- 引用 ----
int& r = x;    // r 是 x 的别名，必须在声明时绑定
r = 100;       // 直接改 x，x == 100
// r = y;      // 这不是「让 r 指向 y」，而是把 y 的值赋给 x！
// 引用一旦绑定，终生不能改绑

// ---- 指针 ----
int* p = &x;   // p 指向 x
*p = 100;      // 改 x，x == 100
p = &y;        // OK！指针可以改指向 y
*p = 200;      // 现在改的是 y，y == 200
p = nullptr;   // 指针可以为空

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};

    int* p = arr;        // 等价于 int* p = &arr[0]; 数组名退化为首元素指针

    cout << *p     << "\n";   // 10     —— arr[0]
    cout << *(p+1) << "\n";   // 20     —— arr[1]
    cout << *(p+2) << "\n";   // 30     —— arr[2]

    // 下面四种写法完全等价：
    cout << arr[2]   << "\n"; // 30
    cout << *(arr+2) << "\n"; // 30
    cout << p[2]     << "\n"; // 30
    cout << *(p+2)   << "\n"; // 30

    return 0;
}

int arr[5] = {10, 20, 30, 40, 50};

// 方式一：传统下标
for (int i = 0; i < 5; i++) cout << arr[i] << " ";
cout << "\n";

// 方式二：指针遍历（理解即可，竞赛中很少这么写）
for (int* p = arr; p < arr + 5; p++) {
    cout << *p << " ";
}
cout << "\n";

#include <bits/stdc++.h>
using namespace std;

// 用指针：传入地址，函数内通过解引用修改原变量
void swapByPointer(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 用引用：更简洁（推荐）
void swapByRef(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int x = 1, y = 2;

    swapByPointer(&x, &y);   // 必须显式传地址 &x, &y
    cout << x << " " << y << "\n";  // 2 1

    swapByRef(x, y);         // 直接传变量
    cout << x << " " << y << "\n";  // 1 2

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 动态分配单个 int
    int* p = new int;     // 在堆上申请一个 int
    *p = 42;
    cout << *p << "\n";   // 42
    delete p;             // 用完必须释放！否则内存泄漏

    // 动态分配数组（运行时才知道大小）
    int n;
    cin >> n;
    int* arr = new int[n];   // 堆上申请 n 个 int
    for (int i = 0; i < n; i++) arr[i] = i * i;
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << "\n";
    delete[] arr;            // 释放数组要用 delete[]（带方括号）！

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void printList(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " ";
    }
    cout << "\n";
}

int length(Node* head) {
    int cnt = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cnt++;
    }
    return cnt;
}

Node* findValue(Node* head, int target) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        if (cur->data == target) return cur;
    }
    return nullptr;
}

int main() {
    Node* head = new Node{1, nullptr};
    head->next = new Node{2, nullptr};
    head->next->next = new Node{3, nullptr};

    printList(head);                 // 1 2 3
    cout << length(head) << "\n";     // 3
    cout << (findValue(head, 2) != nullptr) << "\n";  // 1

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void pushFront(Node*& head, int x) {
    head = new Node{x, head};
}

void pushBack(Node*& head, Node*& tail, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) {
        head = tail = node;
    } else {
        tail->next = node;
        tail = node;
    }
}

void insertAfter(Node* pos, int x) {
    if (pos == nullptr) return;
    pos->next = new Node{x, pos->next};
}

void printList(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " ";
    }
    cout << "\n";
}

int main() {
    Node* head = nullptr;
    Node* tail = nullptr;

    pushBack(head, tail, 1);      // 1
    pushBack(head, tail, 3);      // 1 -> 3
    insertAfter(head, 2);         // 1 -> 2 -> 3
    pushFront(head, 0);           // 0 -> 1 -> 2 -> 3

    printList(head);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void pushBack(Node*& head, Node*& tail, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) {
        head = tail = node;
    } else {
        tail->next = node;
        tail = node;
    }
}

void popFront(Node*& head) {
    if (head == nullptr) return;
    Node* old = head;
    head = head->next;
    delete old;
}

bool eraseValue(Node*& head, int target) {
    if (head == nullptr) return false;
    if (head->data == target) {
        popFront(head);
        return true;
    }

    Node* prev = head;
    Node* cur = head->next;
    while (cur != nullptr) {
        if (cur->data == target) {
            prev->next = cur->next;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->next;
    }
    return false;
}

void printList(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " ";
    }
    cout << "\n";
}

void clearList(Node*& head) {
    while (head != nullptr) {
        popFront(head);
    }
}

int main() {
    Node* head = nullptr;
    Node* tail = nullptr;

    for (int x : {1, 2, 3, 4}) pushBack(head, tail, x);
    printList(head);       // 1 2 3 4

    eraseValue(head, 3);
    printList(head);       // 1 2 4

    popFront(head);
    printList(head);       // 2 4

    clearList(head);
    return 0;
}

struct TreeNode {
    int val;
    TreeNode* left;    // 左孩子（没有则为 nullptr）
    TreeNode* right;   // 右孩子（没有则为 nullptr）
};

// 创建一个节点
TreeNode* root = new TreeNode{1, nullptr, nullptr};
root->left  = new TreeNode{2, nullptr, nullptr};
root->right = new TreeNode{3, nullptr, nullptr};

//        1
//       / \
//      2   3

// ---- 指针版 ----
struct Node { int v; Node* nxt; };
Node* head = new Node{1, nullptr};
head->nxt = new Node{2, nullptr};

// ---- 数组模拟版（竞赛常用）----
const int N = 100005;
int val[N], nxt[N], cnt = 0;   // 下标 0 留作「空」，真实节点从 1 开始
int head = 0;                  // 0 表示空链表

int newNode(int v) {           // 「new」一个节点 → 返回下标
    ++cnt;
    val[cnt] = v;
    nxt[cnt] = 0;
    return cnt;
}

void insertAfter(int pos, int id) {
    nxt[id] = nxt[pos];
    nxt[pos] = id;
}

// 建立 1 -> 2
head = newNode(1);
insertAfter(head, newNode(2));

// 遍历：用下标代替指针，0 代替 nullptr
for (int i = head; i != 0; i = nxt[i]) cout << val[i] << " ";

#include <bits/stdc++.h>
using namespace std;

// 想让函数修改外部指针的指向？传二级指针！
void allocate(int** pp, int n) {
    *pp = new int[n];   // 通过解引用二级指针，修改外部指针
}

int main() {
    int* arr = nullptr;
    allocate(&arr, 5);  // 传 arr 的地址（int**）
    for (int i = 0; i < 5; i++) arr[i] = i * i;
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << "\n";
    delete[] arr;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 3, m = 4;

    // 分配 n 个 int*（每行的指针）
    int** mat = new int*[n];
    for (int i = 0; i < n; i++) {
        mat[i] = new int[m];  // 每行分配 m 个 int
    }

    // 赋值
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            mat[i][j] = i * m + j;

    // 打印
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << setw(3) << mat[i][j];
        cout << "\n";
    }

    // 释放：先释放每一行，再释放行指针数组
    for (int i = 0; i < n; i++) delete[] mat[i];
    delete[] mat;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

// 自己实现 strlen：数到 '\0' 为止
int myStrlen(const char* s) {
    int len = 0;
    while (*s != '\0') {   // 等价于 while (*s)
        len++;
        s++;               // 指针前进到下一个字符
    }
    return len;
}

// 自己实现 strcpy：把 src 复制到 dst
void myStrcpy(char* dst, const char* src) {
    while (*src != '\0') {
        *dst = *src;       // 逐字符复制
        dst++;
        src++;
    }
    *dst = '\0';           // 别忘了末尾的 '\0'！
}

// 更「指针味」的写法——一行搞定：
void myStrcpyV2(char* dst, const char* src) {
    while ((*dst++ = *src++));  // 赋值 + 判断 + 指针前进，一体完成
}

int main() {
    const char* s = "hello";
    cout << myStrlen(s) << "\n";  // 5

    char buf[100];
    myStrcpy(buf, s);
    cout << buf << "\n";          // hello

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

bool cmpAbs(int a, int b) {
    return abs(a) < abs(b);  // 按绝对值升序
}

int main() {
    vector<int> a = {-5, 3, -1, 4, -2};
    sort(a.begin(), a.end(), cmpAbs);  // cmpAbs 作为函数指针传入
    for (int x : a) cout << x << " ";  // -1 -2 3 4 -5
    cout << "\n";
    return 0;
}

思路： 用 &x 给指针赋值，再用 *p 解引用赋值。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 5;
    int* p = &x;    // p 指向 x
    *p = 99;        // 通过指针修改 x
    cout << x << "\n";  // 99
    return 0;
}

关键点：

• int* p = &x;——& 取地址
• *p = 99;——* 解引用，改的是 x 本身

#include <bits/stdc++.h>
using namespace std;

void swp(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int x, y;
    cin >> x >> y;
    swp(&x, &y);    // 注意要传地址
    cout << x << " " << y << "\n";
    return 0;
}

关键点：

• 函数参数是 int*，调用时必须传地址 &x, &y
• 函数内用 *a、*b 访问原变量

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    int* p = arr;           // 数组名退化为首元素指针
    cout << *(p + 2) << "\n";  // 30，等价于 arr[2]
    return 0;
}

关键点：

• p = arr 等价于 p = &arr[0]
• *(p+2) 等价于 p[2]、arr[2]——指针算术按元素大小前进

思路： 函数遍历数组，记录最大元素的地址并返回。

#include <bits/stdc++.h>
using namespace std;

int* findMax(int* arr, int n) {
    int* best = arr;        // 先假设第一个最大
    for (int i = 1; i < n; i++) {
        if (arr[i] > *best) best = &arr[i];
    }
    return best;            // 返回指向最大元素的指针
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int* p = findMax(a.data(), n);  // a.data() 拿到底层数组指针
    cout << *p << "\n";
    return 0;
}

关键点：

• 返回的是「指向数组内某元素」的指针，数组还活着，所以安全（不是返回局部变量地址！）
• a.data()——vector 提供底层连续数组的首指针
• best 始终保存当前最大元素的地址

思路： 双指针，从两端向中间交换，正是第 2.3 章翻转算法的指针版。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int* left = &a[0];
    int* right = &a[n - 1];
    while (left < right) {       // 指针可以直接比较大小
        swap(*left, *right);
        left++;
        right--;
    }

    for (int x : a) cout << x << " ";
    cout << "\n";
    return 0;
}

关键点：

• 同一数组内的指针可以用 <、> 比较位置
• left++ / right-- 让指针按元素前进/后退
• 循环条件 left < right 保证在中点相遇时停止

思路： 边读边在尾部接新节点，再从头遍历求和。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    int n;
    cin >> n;

    Node* head = nullptr;
    Node* tail = nullptr;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node{x, nullptr};
        if (head == nullptr) {      // 第一个节点
            head = tail = node;
        } else {
            tail->next = node;      // 接到尾部
            tail = node;            // 更新尾指针
        }
    }

    long long sum = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        sum += cur->data;
    }
    cout << sum << "\n";

    // 释放
    while (head) { Node* t = head; head = head->next; delete t; }

    return 0;
}

关键点：

• 用 head 和 tail 两个指针，尾插法 O(1) 接节点
• cur = cur->next 是链表遍历的标准写法
• 用完逐个 delete（竞赛中可省，程序结束自动回收）

思路： 三指针法——prev、cur、next。每步把 cur->next 反指向 prev，然后三个指针整体右移。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    // 建立 1→2→3→4→5
    Node* head = nullptr;
    for (int i = 5; i >= 1; i--) {   // 倒着头插，得到正序
        head = new Node{i, head};
    }

    // 反转
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;  // 1. 先存住下一个
        cur->next = prev;        // 2. 当前节点反指向前一个
        prev = cur;              // 3. prev 前进
        cur = next;              // 4. cur 前进
    }
    head = prev;                 // prev 成为新的头

    // 打印
    for (Node* p = head; p; p = p->next) cout << p->data << " ";
    cout << "\n";

    return 0;
}

关键点：

• 反转链表的核心是「先用 next 备份下一个，再改 cur->next 的指向」，顺序不能乱，否则链断了找不回来
• 三指针 prev / cur / next 同步右移，O(N) 时间、O(1) 额外空间
• 这道题是理解指针操作的「试金石」，务必亲手画图走一遍

思路： 快慢指针。若无环，快指针会先到达 nullptr；若有环，快指针会在环里追上慢指针。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // 慢：走 1 步
        fast = fast->next->next;    // 快：走 2 步
        if (slow == fast) return true;  // 相遇 → 有环
    }
    return false;   // fast 到达末尾 → 无环
}

int main() {
    // 构造 1→2→3→4，再让 4 指回 2 形成环
    Node* n1 = new Node{1, nullptr};
    Node* n2 = new Node{2, nullptr};
    Node* n3 = new Node{3, nullptr};
    Node* n4 = new Node{4, nullptr};
    n1->next = n2; n2->next = n3; n3->next = n4;
    n4->next = n2;   // 制造环！

    cout << (hasCycle(n1) ? "YES" : "NO") << "\n";  // YES
    return 0;
}

关键点：

• 循环条件 fast && fast->next 必须双重判空——因为 fast 一次走两步，要确保 fast->next->next 不越过空指针
• 快慢指针是处理链表环、找中点、找倒数第 K 个节点的通用利器
• 若有环，快指针每轮比慢指针多走 1 步，最终必在环内相遇——时间 O(N)，空间 O(1)

思路： 频繁的「移出 + 插入」正是双向链表的拿手好戏——它能 O(1) 完成任意位置的删除和插入，而数组做这件事要 O(N) 搬移。这里用数组模拟双向链表（竞赛主流写法，呼应 2.7.7 的对照表）：pre[i] 和 nxt[i] 分别存编号 i 左右邻居，用哨兵 0 表示队首之前/队尾之后。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int pre[N], nxt[N];   // pre[i]/nxt[i]：编号 i 的前驱/后继；0 为哨兵（队首端/队尾端）

void detach(int x) {          // 把 x 从当前位置摘下
    nxt[pre[x]] = nxt[x];
    pre[nxt[x]] = pre[x];
}
void insertAfter(int y, int x) {  // 把 x 插到 y 的正后方
    int z = nxt[y];           // y 原来的后继
    nxt[y] = x; pre[x] = y;
    nxt[x] = z; pre[z] = x;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 初始队列 1 2 ... n，用哨兵 0 串起两端
    pre[1] = 0; nxt[0] = 1;       // 0 → 1
    for (int i = 1; i < n; i++) { nxt[i] = i + 1; pre[i + 1] = i; }
    nxt[n] = 0; pre[0] = n;       // n → 0（回到哨兵，表示队尾）

    while (m--) {
        int x, y;
        cin >> x >> y;
        detach(x);            // 先把 x 移出原位
        insertAfter(y, x);    // 再插到 y 后面
    }

    // 从哨兵后第一个节点开始，沿 nxt 输出整条队列
    for (int i = nxt[0]; i != 0; i = nxt[i]) {
        cout << i << (nxt[i] ? " " : "\n");
    }
    return 0;
}

关键点：

• 为什么用链表不用数组？ 数组插队要把后面所有元素后移，单次 O(N)，M 次就是 O(NM)；双向链表删除+插入都是 O(1)，总计 O(N+M)，N、M 达 10^5 时差距巨大
• 哨兵 0 让队首/队尾不必特判：nxt[0] 是真正队首，pre[0] 是真正队尾
• 这里以编号本身作下标（编号即「指针」），是数组模拟链表的典型用法——和 2.7.7 的对照表完全一致
• detach 必须在 insertAfter 之前，否则 x 的旧邻居关系还没断开

思路： 指针从首字符出发，逐字符前进，遇到 \0 停止。走过的步数就是长度。

#include <bits/stdc++.h>
using namespace std;

int myStrlen(const char* s) {
    int len = 0;
    while (*s != '\0') {  // 等价于 while (*s)
        len++;
        s++;              // 指针前进到下一个字符
    }
    return len;
}

int main() {
    const char* s = "hello";
    cout << myStrlen(s) << "\n";  // 5
    return 0;
}

关键点：

• *s 解引用取当前字符；s++ 让指针前进（指针算术）
• 循环条件 *s != '\0'——C 风格字符串以 \0 标记结尾
• 这个练习让你体会「指针 + 循环 = 字符串操作」的本质

思路： 两个指针同步前进，逐字符赋值，最后手动补 \0。

#include <bits/stdc++.h>
using namespace std;

void myStrcpy(char* dst, const char* src) {
    while (*src != '\0') {
        *dst = *src;   // 逐字符赋值
        dst++;
        src++;
    }
    *dst = '\0';       // 别忘了末尾的 '\0'！
}

// 精简版（理解原理后再看）：
void myStrcpyV2(char* dst, const char* src) {
    while ((*dst++ = *src++));  // 赋值 + 判断 + 前进，一体完成
}

int main() {
    const char* src = "world";
    char dst[100];
    myStrcpy(dst, src);
    cout << dst << "\n";  // world
    return 0;
}

关键点：

• const char* src——源字符串用 const 修饰，防止误修改
• 必须手动追加 \0，否则 dst 不是合法的 C 字符串
• 精简版 (*dst++ = *src++) 利用后置 ++：先赋值再指针前进，循环到赋值结果为 \0 时自动停止

思路： 用一个「哨兵」哑节点（dummy）简化头处理，维护一个尾指针 tail。每次比较两条链表的当前头节点，把较小的摘下来接到 tail 后面，被摘的那条链表头指针前进。最后把剩余部分直接接上。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* mergeTwoLists(Node* l1, Node* l2) {
    Node dummy{0, nullptr};       // 哑节点，简化头部处理
    Node* tail = &dummy;          // tail 始终指向结果链表的尾

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->data < l2->data) {
            tail->next = l1;      // 摘 l1 当前节点
            l1 = l1->next;        // l1 前进
        } else {
            tail->next = l2;      // 摘 l2 当前节点
            l2 = l2->next;        // l2 前进
        }
        tail = tail->next;        // tail 始终保持在尾部
    }

    // 把剩余的链表直接接上（最多一条非空）
    tail->next = (l1 != nullptr) ? l1 : l2;

    return dummy.next;            // 跳过哑节点，返回真正的头
}

int main() {
    // 构建 L1: 1→3→5
    Node* l1 = new Node{1, new Node{3, new Node{5, nullptr}}};
    // 构建 L2: 2→4→6
    Node* l2 = new Node{2, new Node{4, new Node{6, nullptr}}};

    Node* merged = mergeTwoLists(l1, l2);

    for (Node* p = merged; p; p = p->next)
        cout << p->data << " ";
    cout << "\n";  // 1 2 3 4 5 6

    return 0;
}

关键点：

• 哑节点（dummy node） 是链表题的经典技巧——避免当头节点为空时的特判
• tail 始终保持指向结果链表的最后一个节点，接新节点时 O(1)
• 指针操作的核心：改了 tail->next 后必须同步更新 tail 和被摘链表的头指针
• 这是合并（Merge）、链表归并排序（Merge Sort）的基础子操作

思路： 慢指针每次走 1 步，快指针每次走 2 步。当快指针到达末尾时，慢指针正好在中点。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* findMiddle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // 慢：1 步
        fast = fast->next->next;    // 快：2 步
    }
    return slow;  // fast 到末尾时，slow 就是中点
}

int main() {
    // 测试 1: 1→2→3→4→5（奇数）
    Node* head1 = new Node{1, new Node{2, new Node{3,
                        new Node{4, new Node{5, nullptr}}}}};
    cout << findMiddle(head1)->data << "\n";  // 3

    // 测试 2: 1→2→3→4（偶数）
    Node* head2 = new Node{1, new Node{2, new Node{3,
                        new Node{4, nullptr}}}};
    cout << findMiddle(head2)->data << "\n";  // 3

    return 0;
}

关键点：

• 快慢指针是处理链表「中点」「倒数第 K 个」「环检测」的通用利器，时间 O(N)、空间 O(1)
• 循环条件 fast && fast->next——因为快指针一次走两步，两个判空缺一不可
• 当 fast == nullptr（奇数长度）或 fast->next == nullptr（偶数长度）时循环退出，slow 恰好在中点
• 如果想要第一个中间节点（偶数长度时返回靠前那个），可以让快指针先走一步：fast = head->next