• C++

  • GESP五级｜单链表、双向链表、循环链表 零基础竞赛教程

  • @ 2026-7-31 20:23:26

GESP五级｜单链表、双向链表、循环链表 零基础竞赛教程

前置说明

链表属于 GESP C++五级数据结构考点，信奥入门基础内容。 数组：内存连续，随机访问快；插入删除中间元素需要大量移动数据。 链表：内存分散存放，依靠指针相连；访问元素需要从头遍历；任意位置插入、删除效率更高。

名词通俗解释 结点：存放数据 + 指针的组合单元 指针：记录下一个结点在哪里

一、单链表（基础必考）

通俗原理

每个结点包含两部分：数据 + 后继指针（指向下一个结点） 最后一个结点指针置空 NULL，代表链表结束。 只能从头向后遍历，不能反向走。

结构体定义

#include <iostream>
using namespace std;

// 定义单链表结点
struct Node
{
    int data;        // 结点存储的数据
    Node* next;      // 指向下一个结点的指针
    // 构造函数，快速创建结点
    Node(int val) : data(val), next(NULL) {}
};

int main()
{
    // 1. 创建结点
    Node* n1 = new Node(10);
    Node* n2 = new Node(20);
    Node* n3 = new Node(30);

    // 2. 连接结点，构建链表 10 -> 20 -> 30
    n1->next = n2;
    n2->next = n3;
    n3->next = NULL; // 尾结点，无后续

    // 3. 遍历链表
    Node* p = n1;
    while(p != NULL)
    {
        cout << p->data << " ";
        p = p->next; // 指针走到下一个结点
    }
    cout << endl;

    // 释放内存（竞赛可省略，工程规范要求）
    delete n1; delete n2; delete n3;
    return 0;
}

封装常用操作完整版（带注释，考场模板）

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* next;
    Node(int val) : data(val), next(NULL) {}
};

// 在链表尾部插入结点
void insertTail(Node* &head, int val)
{
    Node* newnode = new Node(val);
    if(head == NULL) // 链表为空
    {
        head = newnode;
        return;
    }
    Node* p = head;
    while(p->next != NULL) // 找到最后一个结点
    {
        p = p->next;
    }
    p->next = newnode;
}

// 删除指定数值结点
void removeVal(Node* &head, int val)
{
    if(head == NULL) return;
    // 头结点就是目标
    if(head->data == val)
    {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* p = head;
    // 找到待删除结点的前驱
    while(p->next != NULL && p->next->data != val)
    {
        p = p->next;
    }
    if(p->next == NULL) return; // 没找到
    Node* temp = p->next;
    p->next = p->next->next;
    delete temp;
}

// 遍历输出链表
void printList(Node* head)
{
    Node* p = head;
    while(p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main()
{
    Node* head = NULL; // 链表头指针，初始空链表
    insertTail(head, 1);
    insertTail(head, 2);
    insertTail(head, 3);
    printList(head);

    removeVal(head, 2);
    printList(head);
    return 0;
}

✅优点：结构最简单，代码短 ❌缺点：只能向后遍历；删除结点必须先找到前驱结点

二、双向链表（双链表，五级重点）

通俗原理

每个结点包含三部分：数据 + 前驱指针 + 后继指针 可以向前、向后双向遍历；删除结点不需要单独查找前驱。 头结点前驱 = NULL，尾结点后继 = NULL。

完整带注释模板

#include <iostream>
using namespace std;

// 双向链表结点
struct DNode
{
    int data;
    DNode* prev;  // 指向前一个结点
    DNode* next;  // 指向下一个结点
    DNode(int val) : data(val), prev(NULL), next(NULL) {}
};

// 尾部插入
void insertTail(DNode* &head, int val)
{
    DNode* newnode = new DNode(val);
    if(head == NULL)
    {
        head = newnode;
        return;
    }
    DNode* p = head;
    while(p->next != NULL)
    {
        p = p->next;
    }
    p->next = newnode;
    newnode->prev = p; // 新结点向前绑定
}

// 删除指定数值结点
void removeVal(DNode* &head, int val)
{
    if(head == NULL) return;
    DNode* p = head;
    while(p != NULL && p->data != val)
    {
        p = p->next;
    }
    if(p == NULL) return; // 不存在

    // 情况1：待删结点是头结点
    if(p->prev == NULL)
    {
        head = p->next;
    }
    else
    {
        p->prev->next = p->next;
    }
    // 情况2：待删结点不是尾结点
    if(p->next != NULL)
    {
        p->next->prev = p->prev;
    }
    delete p;
}

// 正向遍历
void printForward(DNode* head)
{
    DNode* p = head;
    while(p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main()
{
    DNode* head = NULL;
    insertTail(head,10);
    insertTail(head,20);
    insertTail(head,30);
    printForward(head);

    removeVal(head,20);
    printForward(head);
    return 0;
}

✅优点：双向行走；删除操作更方便 ❌缺点：每个结点多存一个指针，占用更多内存

三、循环链表（单循环链表，竞赛常用版本）

通俗原理

基于单链表改造：尾结点不再指向NULL，尾结点next指向头结点 链表首尾相连，形成圆环，可以无限循环遍历。

注意：遍历必须记录起点，否则死循环！

完整带注释模板

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* next;
    Node(int val) : data(val), next(NULL) {}
};

// 尾部插入，构建循环链表
void insertTailCircle(Node* &head, int val)
{
    Node* newnode = new Node(val);
    if(head == NULL)
    {
        head = newnode;
        newnode->next = head; // 唯一结点，自环
        return;
    }
    Node* p = head;
    // 找到尾结点（next指向head）
    while(p->next != head)
    {
        p = p->next;
    }
    p->next = newnode;
    newnode->next = head; // 新尾结点指向头
}

// 遍历循环链表，从head开始
void printCircle(Node* head)
{
    if(head == NULL) return;
    Node* p = head;
    do
    {
        cout << p->data << " ";
        p = p->next;
    }while(p != head); // 回到起点停止，防止死循环
    cout << endl;
}

int main()
{
    Node* head = NULL;
    insertTailCircle(head, 1);
    insertTailCircle(head, 2);
    insertTailCircle(head, 3);
    printCircle(head);
    return 0;
}

✅优点：可以从任意位置遍历整条链表；适合环形问题（约瑟夫环经典题） ❌缺点：一不小心写出无限循环，边界判断要小心

四、三种链表对比（五级选择题考点）

  1. 单链表 结点：数据 + next指针 遍历方向：只能向后 适用：简单增删、基础链表题目

  2. 双向链表 结点：data + prev + next 遍历方向：向前、向后双向 适用：需要频繁查找前驱、双向访问场景

  3. 循环单链表 结点：data + next 尾结点指向头结点，形成环 适用：环形模拟，经典【约瑟夫问题】

五、GESP五级考场0基础避坑指南

  1. 指针操作最容易出错，修改指针顺序不能颠倒；
  2. 使用 new 创建结点，删除使用 delete；竞赛时间紧张内存泄漏一般不扣分；
  3. 循环链表遍历一定要设置终止条件，禁止无限循环；
  4. 双向链表删除结点时，前后两条指针都要修改，漏一条链表断裂；
  5. 传递头指针建议使用引用 Node* &head，否则函数内修改无法对外生效；
  6. 访问指针成员务必用 ->；普通变量用 .，不要混用。

六、竞赛高频考题方向

  1. 链表遍历、查找指定数值
  2. 头部/尾部插入、按位置删除结点
  3. 链表反转（单链表高频大题）
  4. 循环链表实现约瑟夫环（GESP五级压轴题型）

2 条评论

  • @ 2026-7-31 20:25:42

    C++链表零基础完整教程：单链表｜双向链表｜循环单链表

    学习顺序建议：单链表 → 双向链表 → 循环链表 核心概念：链表由**节点(Node)**串联而成；每个节点存放【数据】+【指针】。 数组：连续内存；链表：分散内存，依靠指针相连；优势：任意位置插入/删除不需要大规模移动元素

    通用前置知识

    结构体节点、指针基础

    // 指针复习：Node *p 代表p存储节点地址，*p代表节点本体
// p->data   等价于 (*p).data
// new Node() 新建节点；delete p 释放节点（防止内存泄漏）

    一、单链表（最基础）

    结构： [数据|下一个节点地址] → [数据|下一个节点地址] → nullptr 尾节点指针 = nullptr，代表链表结束。

    常用操作清单

    1. 头插法（头部新增节点）
    2. 尾插法（尾部新增节点）
    3. 遍历输出链表
    4. 根据数值删除节点
    5. 销毁链表

    完整带注释代码

    #include <iostream>
using namespace std;

// 定义单链表节点
struct Node
{
    int data;        // 存放数据
    Node *next;      // 指向下一个节点的指针
    // 构造函数，方便快速创建节点
    Node(int val)
    {
        data = val;
        next = nullptr;
    }
};

// 头插：在链表最前面插入数值val
void headInsert(Node *&head, int val)
{
    Node *new_node = new Node(val);
    new_node->next = head; // 新节点指向原来第一个节点
    head = new_node;       // 头指针更新为新节点
}

// 尾插：在链表末尾插入数值val
void tailInsert(Node *&head, int val)
{
    Node *new_node = new Node(val);
    // 如果链表为空
    if (head == nullptr)
    {
        head = new_node;
        return;
    }
    // 找到最后一个节点
    Node *p = head;
    while (p->next != nullptr)
    {
        p = p->next;
    }
    p->next = new_node;
}

// 遍历打印链表
void printList(Node *head)
{
    Node *p = head;
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 删除第一个值为val的节点
void delNode(Node *&head, int val)
{
    if (head == nullptr) return;

    // 情况1：要删除的是头节点
    if (head->data == val)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
        return;
    }

    // 情况2：删除中间/尾部节点
    Node *p = head;
    // 找到待删除节点的前一个节点
    while (p->next != nullptr && p->next->data != val)
    {
        p = p->next;
    }
    if (p->next == nullptr) return; // 没找到

    Node *temp = p->next;
    p->next = p->next->next;
    delete temp;
}

// 释放所有节点，防止内存泄漏
void destroyList(Node *&head)
{
    Node *p = head;
    while (p != nullptr)
    {
        Node *temp = p;
        p = p->next;
        delete temp;
    }
    head = nullptr;
}

int main()
{
    Node *head = nullptr; // 初始链表为空

    tailInsert(head, 10);
    tailInsert(head, 20);
    tailInsert(head, 30);
    cout << "原始链表：";
    printList(head); // 10 20 30

    headInsert(head, 5);
    cout << "头插5后：";
    printList(head); // 5 10 20 30

    delNode(head, 20);
    cout << "删除20后：";
    printList(head); // 5 10 30

    destroyList(head);
    return 0;
}

    单链表缺点

    只能向后遍历；删除当前节点必须先找到前驱节点，无法直接找到上一个节点。

    二、双向链表（双链表）

    结构： nullptr ← [前驱|数据|后继] ↔ [前驱|数据|后继] ↔ [前驱|数据|后继] → nullptr 每个节点两个指针：

    • prev：指向前一个节点
    • next：指向下一个节点

    优点：可以向前、向后双向遍历；删除节点不用单独寻找前驱

    #include <iostream>
using namespace std;

// 双向链表节点
struct DNode
{
    int data;
    DNode *prev;   // 前驱指针
    DNode *next;   // 后继指针
    DNode(int val)
    {
        data = val;
        prev = nullptr;
        next = nullptr;
    }
};

// 尾插
void tailInsert(DNode *&head, int val)
{
    DNode *new_node = new DNode(val);
    if (head == nullptr)
    {
        head = new_node;
        return;
    }
    DNode *p = head;
    while (p->next != nullptr)
        p = p->next;

    p->next = new_node;
    new_node->prev = p;
}

// 正向遍历
void printForward(DNode *head)
{
    DNode *p = head;
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 反向遍历（双链表独有！单链表做不到）
void printBackward(DNode *head)
{
    if (head == nullptr) return;
    DNode *p = head;
    // 走到尾部
    while (p->next != nullptr)
        p = p->next;
    // 向前走
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->prev;
    }
    cout << endl;
}

// 删除值为val的节点
void delDNode(DNode *&head, int val)
{
    if (head == nullptr) return;
    DNode *p = head;
    while (p != nullptr && p->data != val)
        p = p->next;
    if (p == nullptr) return; // 找不到

    // 情况1：待删节点是头节点
    if (p->prev == nullptr)
    {
        head = p->next;
        if (head != nullptr)
            head->prev = nullptr;
    }
    // 情况2：中间/尾部节点
    else
    {
        p->prev->next = p->next;
        if (p->next != nullptr)
            p->next->prev = p->prev;
    }
    delete p;
}

// 销毁链表
void destroyDList(DNode *&head)
{
    DNode *p = head;
    while (p != nullptr)
    {
        DNode *temp = p;
        p = p->next;
        delete temp;
    }
    head = nullptr;
}

int main()
{
    DNode *head = nullptr;
    tailInsert(head, 1);
    tailInsert(head, 2);
    tailInsert(head, 3);

    cout << "正向：";
    printForward(head);  // 1 2 3
    cout << "反向：";
    printBackward(head); // 3 2 1

    delDNode(head, 2);
    cout << "删除2，正向：";
    printForward(head); //1 3

    destroyDList(head);
    return 0;
}

    双向链表注意点

    插入、删除操作需要同时维护 prev 和 next 两个指针，容易漏写导致断链！

    三、循环单链表（常用循环链表；零基础先学这个，循环双链表作为拓展）

    普通单链表尾节点next=nullptr 循环单链表：尾节点的next指向头节点，形成环形！

    示意图：头→节点2→节点3→头

    特点：没有nullptr，遍历终止条件：回到头节点

    #include <iostream>
using namespace std;

struct CNode
{
    int data;
    CNode *next;
    CNode(int val)
    {
        data = val;
        next = nullptr;
    }
};

// 尾插法（循环单链表）
void tailInsertCircle(CNode *&head, int val)
{
    CNode *new_node = new CNode(val);
    // 空链表
    if (head == nullptr)
    {
        head = new_node;
        new_node->next = head; // 自环
        return;
    }
    // 找到尾部：next != head
    CNode *p = head;
    while (p->next != head)
    {
        p = p->next;
    }
    p->next = new_node;
    new_node->next = head;
}

// 遍历循环链表
void printCircle(CNode *head)
{
    if (head == nullptr) return;
    CNode *p = head;
    do
    {
        cout << p->data << " ";
        p = p->next;
    } while (p != head); // 回到头节点停止
    cout << endl;
}

// 删除指定数值节点
void delCircleNode(CNode *&head, int val)
{
    if (head == nullptr) return;

    CNode *p = head;
    CNode *pre = nullptr;
    // 寻找目标节点
    do
    {
        if (p->data == val) break;
        pre = p;
        p = p->next;
    } while (p != head);

    if (p->data != val) return; // 未找到

    // 情况1：链表只有一个节点
    if (p->next == head && pre == nullptr)
    {
        delete p;
        head = nullptr;
        return;
    }

    // 情况2：删除头节点
    if (p == head)
    {
        // 先找到尾节点
        CNode *tail = head;
        while (tail->next != head)
            tail = tail->next;
        head = head->next;
        tail->next = head;
    }
    else
    {
        // 删除中间/尾部节点
        pre->next = p->next;
    }
    delete p;
}

// 释放循环链表
void destroyCircle(CNode *&head)
{
    if (head == nullptr) return;
    CNode *p = head;
    CNode *temp;
    do
    {
        temp = p;
        p = p->next;
        delete temp;
    } while (p != head);
    head = nullptr;
}

int main()
{
    CNode *head = nullptr;
    tailInsertCircle(head,10);
    tailInsertCircle(head,20);
    tailInsertCircle(head,30);
    cout << "循环链表：";
    printCircle(head); //10 20 30

    delCircleNode(head, 20);
    cout << "删除20：";
    printCircle(head); //10 30

    destroyCircle(head);
    return 0;
}

    循环链表经典场景

    约瑟夫环问题（报数出圈），最适合使用循环链表。

    三大链表横向对比表

    类型 指针数量 遍历方向 尾部标记 难度 特点
    单链表 1(next) 只能向后 nullptr ⭐ 代码最简单，删除需要前驱
    双向链表 2(prev+next) 向前+向后 ⭐⭐⭐ 操作灵活，维护两个指针
    循环单链表 1(next) 向后循环 尾→头 ⭐⭐ 环形结构，约瑟夫环专用

    📌 零基础学习重点&踩坑提醒

    1. 引用 Node *&head 函数内部修改头指针必须加引用，否则修改无效！
    2. 链表遍历循环条件不要写死，区分普通链表 p!=nullptr 和循环链表 p!=head
    3. 删除节点务必使用delete释放内存，竞赛不强制，但正规写法必须写
    4. 插入节点顺序不能颠倒！指针赋值顺序错直接断链

    带头结点链表模板（竞赛首选）

    什么是头结点？ 在链表最前方额外放一个不存储有效数据的节点，head永远指向它。 ✅优势：所有插入、删除操作统一逻辑，不需要单独判断是否操作头节点，大幅减少分支代码，考场不容易写错。

    一、带头结点 · 单链表

    #include <iostream>
using namespace std;

// 节点定义
struct Node
{
    int data;
    Node *next;
    Node(int val)
    {
        data = val;
        next = nullptr;
    }
};

// 创建带头结点的空链表
Node* createList()
{
    // head是头结点，不存数据
    Node *head = new Node(-1);
    head->next = nullptr;
    return head;
}

// 尾插法
void tailInsert(Node *head, int val)
{
    Node *new_node = new Node(val);
    Node *p = head;
    // 找到最后一个有效节点
    while(p->next != nullptr)
        p = p->next;
    p->next = new_node;
}

// 在pos位置后插入val（pos为数值）
void insertAfter(Node *head, int pos, int val)
{
    Node *p = head->next;
    while(p != nullptr && p->data != pos)
        p = p->next;
    if(p == nullptr) return;

    Node *new_node = new Node(val);
    new_node->next = p->next;
    p->next = new_node;
}

// 删除第一个值为val的节点
void delNode(Node *head, int val)
{
    Node *p = head;
    // p停在目标节点的前驱
    while(p->next != nullptr && p->next->data != val)
        p = p->next;
    if(p->next == nullptr) return;

    Node *temp = p->next;
    p->next = temp->next;
    delete temp;
}

// 遍历输出（跳过头结点）
void printList(Node *head)
{
    Node *p = head->next;
    while(p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 销毁链表（包括头结点）
void destroyList(Node *head)
{
    Node *p = head;
    while(p != nullptr)
    {
        Node *temp = p;
        p = p->next;
        delete temp;
    }
}

int main()
{
    Node *head = createList();
    tailInsert(head,10);
    tailInsert(head,20);
    tailInsert(head,30);
    cout << "初始链表：";
    printList(head);

    insertAfter(head,20,25);
    cout << "20后面插入25：";
    printList(head);

    delNode(head,10);
    cout << "删除10：";
    printList(head);

    destroyList(head);
    return 0;
}

    二、带头结点 · 双向链表

    #include <iostream>
using namespace std;

struct DNode
{
    int data;
    DNode *prev;
    DNode *next;
    DNode(int val)
    {
        data = val;
        prev = nullptr;
        next = nullptr;
    }
};

// 创建带头结点空双链表
DNode* createDList()
{
    DNode *head = new DNode(-1);
    head->prev = nullptr;
    head->next = nullptr;
    return head;
}

// 尾插
void tailInsert(DNode *head, int val)
{
    DNode *new_node = new DNode(val);
    DNode *p = head;
    while(p->next != nullptr)
        p = p->next;

    p->next = new_node;
    new_node->prev = p;
}

// 删除值val节点
void delDNode(DNode *head, int val)
{
    DNode *p = head->next;
    while(p != nullptr && p->data != val)
        p = p->next;
    if(p == nullptr) return;

    p->prev->next = p->next;
    if(p->next != nullptr)
        p->next->prev = p->prev;
    delete p;
}

// 正向打印
void printForward(DNode *head)
{
    DNode *p = head->next;
    while(p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void destroyDList(DNode *head)
{
    DNode *p = head;
    while(p != nullptr)
    {
        DNode *temp = p;
        p = p->next;
        delete temp;
    }
}

int main()
{
    DNode *head = createDList();
    tailInsert(head,1);
    tailInsert(head,2);
    tailInsert(head,3);
    cout << "正向：";
    printForward(head);

    delDNode(head,2);
    cout << "删除2：";
    printForward(head);

    destroyDList(head);
    return 0;
}

    三、带头结点 · 循环单链表

    #include <iostream>
using namespace std;

struct CNode
{
    int data;
    CNode *next;
    CNode(int val)
    {
        data = val;
        next = nullptr;
    }
};

// 创建带头结点循环链表
CNode* createCircle()
{
    CNode *head = new CNode(-1);
    head->next = head; // 头结点自环
    return head;
}

// 尾插
void tailInsert(CNode *head, int val)
{
    CNode *new_node = new CNode(val);
    CNode *p = head;
    while(p->next != head)
        p = p->next;

    p->next = new_node;
    new_node->next = head;
}

// 删除节点
void delCircleNode(CNode *head, int val)
{
    CNode *p = head;
    while(p->next != head && p->next->data != val)
        p = p->next;
    if(p->next == head) return;

    CNode *temp = p->next;
    p->next = temp->next;
    delete temp;
}

void printCircle(CNode *head)
{
    CNode *p = head->next;
    while(p != head)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void destroyCircle(CNode *head)
{
    CNode *p = head->next;
    while(p != head)
    {
        CNode *temp = p;
        p = p->next;
        delete temp;
    }
    delete head;
}

int main()
{
    CNode *head = createCircle();
    tailInsert(head,10);
    tailInsert(head,20);
    tailInsert(head,30);
    cout << "循环链表：";
    printCircle(head);

    delCircleNode(head,20);
    cout << "删除20：";
    printCircle(head);

    destroyCircle(head);
    return 0;
}

    📌 无头结点 VS 带头结点总结

    1. 无头结点（之前版本） 空链表：head=nullptr；插入头部、删除头部需要单独判断，分支多。适合理解原理，不推荐竞赛做题。
    2. 带头结点（本套代码） 链表永远不会head=nullptr；所有操作代码统一，不需要特殊处理首元素。信奥/GESP竞赛优先写这种！

    学习建议

    先跑通【带头结点单链表】，吃透后再学习双向、循环版本。

    • @ 2026-7-31 20:24:12

      追加内容：单链表反转 + 约瑟夫环（循环链表实现）

      承接上文GESP五级链表教程，代码全部详细注释，0基础可读，竞赛直接默写。

      一、单链表反转（GESP五级经典大题）

      思路通俗讲解

      准备三个指针：前驱pre、当前cur、后继nxt。 依次改变每个结点next指针方向，让链表掉头。

      #include <iostream>
using namespace std;

// 单链表结点
struct Node
{
    int data;
    Node* next;
    Node(int val) : data(val), next(NULL) {}
};

// 尾部插入结点
void insertTail(Node* &head, int val)
{
    Node* newnode = new Node(val);
    if (head == NULL)
    {
        head = newnode;
        return;
    }
    Node* p = head;
    while (p->next != NULL)
        p = p->next;
    p->next = newnode;
}

// 链表遍历输出
void printList(Node* head)
{
    Node* p = head;
    while (p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 反转单链表，返回新链表头结点
Node* reverseList(Node* head)
{
    Node* pre = NULL;    // 当前结点的前一个结点
    Node* cur = head;    // 当前正在操作的结点
    Node* nxt = NULL;    // 保存下一个结点，防止断链

    while (cur != NULL)
    {
        nxt = cur->next;  // 先记下后面的结点，防止链表断掉
        cur->next = pre;  // 反转：当前结点指向前面
        pre = cur;        // pre往前走一步
        cur = nxt;        // cur往前走一步
    }
    return pre; // 循环结束pre是新头结点
}

int main()
{
    Node* head = NULL;
    insertTail(head, 1);
    insertTail(head, 2);
    insertTail(head, 3);
    insertTail(head, 4);

    cout << "原链表：";
    printList(head);

    head = reverseList(head);
    cout << "反转后：";
    printList(head);

    return 0;
}

      考场易错提醒

      1. 一定要先用nxt = cur->next保存后继，修改指针后无法找到后续结点；
      2. 最终返回值是pre，不是cur；
      3. 空链表、只有1个结点的链表代码可以自动兼容，无需额外特判。

      二、循环链表实现约瑟夫环（GESP五级压轴题型）

      题目通俗描述

      n个人围成一圈，从第一个开始报数，报到k的人出局；下一个人重新开始报数，不断循环，求出最后剩下人的编号。

      #include <iostream>
using namespace std;

// 循环链表结点
struct Node
{
    int id;        // 人的编号
    Node* next;
    Node(int val) : id(val), next(NULL) {}
};

// 创建n个人的循环链表
Node* createCircle(int n)
{
    if (n <= 0) return NULL;
    Node* head = new Node(1);
    Node* tail = head;
    // 依次创建2~n号结点
    for (int i = 2; i <= n; i++)
    {
        Node* newnode = new Node(i);
        tail->next = newnode;
        tail = newnode;
    }
    tail->next = head; // 尾结点连回头，形成环
    return head;
}

// 约瑟夫环模拟：n人，数k出局
int Josephus(int n, int k)
{
    Node* head = createCircle(n);
    Node* p = head;

    // 找到尾结点（head前一个结点，方便删除）
    while (p->next != head)
        p = p->next;

    // 剩余人数大于1就持续淘汰
    while (p->next != p)
    {
        // 向后走k-1次，到达要删除结点的前驱
        for (int i = 1; i < k; i++)
        {
            p = p->next;
        }
        Node* del = p->next;        // 需要淘汰的结点
        cout << "出局：" << del->id << endl;
        p->next = del->next;        // 跳过被删除结点
        delete del;                 // 释放结点
    }
    int ans = p->id;
    delete p;
    return ans;
}

int main()
{
    int n, k;
    cout << "输入人数n、报数上限k：";
    cin >> n >> k;
    int last = Josephus(n, k);
    cout << "最后留下编号：" << last << endl;
    return 0;
}

      运行示例

      输入：5 3 输出顺序出局：3，1，5，2；最后剩余：4

      考场重点提示

      1. 保存待删除结点的前驱结点，才能修改链表指针；
      2. 循环终止条件：p->next == p，只剩最后一个结点；
      3. 不要直接从目标结点开始遍历，无法完成删除操作。

      拓展小结（选择题考点）

      1. 单链表反转：三指针迭代写法是竞赛首选，递归写法理解难度高，考场优先迭代；
      2. 约瑟夫环两种解法：小规模用循环链表模拟；超大范围用数学递推公式；GESP五级一般考察链表模拟版本。
      • 1
      460
      已通过
      0
      题解被赞
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      4. 在线咨询
      5. Worker 0, 29ms
      6. Powered by Hydro v4.13.3 Community