链表
单链表、双向链表、循环链表

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

int main() {
    // 建一条单链表：1 -> 2 -> 3
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    Node* P = head->next;        // P 指向节点 2
    Node* S = new Node(99);      // 待插入的新节点

    S->next = P->next;           // ← 这里填 S->next = P->next（先接住后半段）
    P->next = S;                 // ← 这里填 P->next = S（再挂上新节点）

    for (Node* p = head; p != nullptr; p = p->next)
        cout << p->val << " ";
    cout << endl;                // 输出：1 2 99 3
    return 0;
}

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        Node* next = cur->next;  // 暂存后继
        cur->next = prev;         // 反转指针
        prev = cur;               // prev 前进
        cur = next;               // cur 前进
    }
    return prev;  // 新的头节点
}

Node* merge(Node* a, Node* b) {
    Node dummy(0);
    Node* tail = &dummy;
    while (a && b) {
        if (a->data <= b->data) {
            tail->next = a; a = a->next;
        } else {
            tail->next = b; b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

#include <iostream>
using namespace std;

struct Node {                 // 双向链表结点
    int val;
    Node *pre, *nxt;
    Node(int v) : val(v), pre(nullptr), nxt(nullptr) {}
};

const int N = 100005;
Node* pos[N];                 // pos[i] 指向编号为 i 的同学
bool alive[N];                // 该同学是否还在队列里

int main() {
    int n;
    cin >> n;
    Node* head = new Node(1);      // 先把 1 号同学放进队列
    pos[1] = head;
    alive[1] = true;

    for (int i = 2; i <= n; i++) {
        int k, p;
        cin >> k >> p;
        Node* cur = new Node(i);
        pos[i] = cur;
        alive[i] = true;
        Node* t = pos[k];
        if (p == 0) {                  // i 站到 k 的左边
            cur->pre = t->pre;
            cur->nxt = t;
            if (t->pre) t->pre->nxt = cur;
            t->pre = cur;
            if (t == head) head = cur; // k 原来是队头，队头换成 i
        } else {                       // i 站到 k 的右边
            cur->nxt = t->nxt;
            cur->pre = t;
            if (t->nxt) t->nxt->pre = cur;
            t->nxt = cur;
        }
    }

    int m;
    cin >> m;
    while (m--) {
        int x;
        cin >> x;
        if (!alive[x]) continue;       // 已经离开队列，忽略这条指令
        alive[x] = false;
        Node* t = pos[x];
        if (t->pre) t->pre->nxt = t->nxt;
        if (t->nxt) t->nxt->pre = t->pre;
        if (t == head) head = t->nxt;  // 删掉的正好是队头
    }

    for (Node* q = head; q != nullptr; q = q->nxt)  // 从左到右输出
        cout << q->val << " ";
    cout << endl;                      // 样例输出：2 4 1
    return 0;
}

#include <iostream>
using namespace std;

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

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

    // 1. 先建一条普通单链表 1 -> 2 -> ... -> n
    Node* head = new Node{1, nullptr};
    Node* tail = head;
    for (int i = 2; i <= n; i++) {
        tail->next = new Node{i, nullptr};
        tail = tail->next;
    }
    tail->next = head;              // 尾巴指回头 → 循环链表

    // 2. 报数出圈
    Node* cur = head;               // 当前数到谁
    Node* prev = tail;              // cur 的前驱，方便删除
    for (int k = 0; k < n; k++) {
        for (int step = 1; step < m; step++) {   // 走 m-1 步
            prev = cur;
            cur = cur->next;
        }
        cout << cur->val << " ";    // 报到 m 的人出圈
        prev->next = cur->next;     // 从链表里摘掉 cur
        Node* nxt = cur->next;
        delete cur;
        cur = nxt;
    }
    cout << endl;                   // n=10, m=3 → 3 6 9 2 7 1 8 5 10 4
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;

const int MAXW = 1005;
bool inMem[MAXW];        // 某单词当前是否在内存里

int main() {
    int cap, len;        // 内存容量、文章单词个数
    cin >> cap >> len;

    queue<int> q;        // 内存中的单词，队头是最早进来的
    int ans = 0;         // 查词典的次数
    for (int i = 0; i < len; i++) {
        int w;
        cin >> w;
        if (!inMem[w]) {                 // 内存里没有，必须查词典
            ans++;
            if ((int)q.size() == cap) {  // 内存满了，先挤掉最早进来的
                inMem[q.front()] = false;
                q.pop();
            }
            q.push(w);                   // 新单词进队尾
            inMem[w] = true;
        }
    }
    cout << ans << endl;   // 样例 3 7 / 1 2 1 5 4 4 1 → 5
    return 0;
}

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// 合并两条已经有序的链表
Node* merge(Node* a, Node* b) {
    Node dummy(0);
    Node* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;          // 剩下的一截直接接上
    return dummy.next;
}

// 链表归并排序
Node* sortList(Node* head) {
    if (!head || !head->next) return head;   // 0 或 1 个结点天然有序
    Node* slow = head;                       // 快慢指针找中点
    Node* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node* mid = slow->next;
    slow->next = nullptr;                    // 从中间断开成两半
    return merge(sortList(head), sortList(mid));
}

int main() {
    int a[] = {4, 2, 1, 3, 5};
    Node dummy(0);
    Node* tail = &dummy;
    for (int x : a) { tail->next = new Node(x); tail = tail->next; }

    for (Node* p = sortList(dummy.next); p; p = p->next)
        cout << p->val << " ";
    cout << endl;                            // 输出：1 2 3 4 5
    return 0;
}

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// 有环则返回环的入口结点，无环返回 nullptr
Node* detectCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;             // 慢指针每次走 1 步
        fast = fast->next->next;       // 快指针每次走 2 步
        if (slow == fast) {            // 相遇 → 说明有环
            Node* p = head;            // 一个指针从起点出发
            while (p != slow) {        // 另一个从相遇点出发，同速前进
                p = p->next;
                slow = slow->next;
            }
            return p;                  // 再次相遇处就是环的入口
        }
    }
    return nullptr;                    // 快指针走到头 → 没有环
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = head->next;   // 4 号指回 2 号，形成环

    Node* entry = detectCycle(head);
    if (entry) cout << "有环，入口结点是 " << entry->val << endl;  // 有环，入口结点是 2
    else       cout << "无环" << endl;
    return 0;
}

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

Node* reverseKGroup(Node* head, int k) {
    Node dummy(0);
    dummy.next = head;
    Node* groupPrev = &dummy;              // 上一组的尾巴
    while (true) {
        // 1. 找到这一组的第 k 个结点
        Node* node = groupPrev;
        for (int i = 0; i < k && node; i++) node = node->next;
        if (!node) break;                  // 不足 k 个，剩下的不动
        Node* groupNext = node->next;      // 下一组的开头

        // 2. 组内反转（头插法反过来）
        Node* prev = groupNext;
        Node* cur = groupPrev->next;
        while (cur != groupNext) {
            Node* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }

        // 3. 重新接回主链
        Node* oldHead = groupPrev->next;   // 反转后它变成这一组的尾巴
        groupPrev->next = prev;            // 反转后的组头
        groupPrev = oldHead;
    }
    return dummy.next;
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    Node dummy(0);
    Node* tail = &dummy;
    for (int x : a) { tail->next = new Node(x); tail = tail->next; }

    for (Node* p = reverseKGroup(dummy.next, 2); p; p = p->next)
        cout << p->val << " ";
    cout << endl;                          // k=2 输出：2 1 4 3 5
    return 0;
}