C++ 链表插入操作 - 代码详解及优化 - 常规

C++ 链表插入操作 - 代码详解及优化

本文将详细介绍使用 C++ 实现链表插入操作的代码，并对代码进行优化，使之更易于理解和维护。同时，提供了示例代码和详细的注释，帮助您快速掌握链表插入操作的实现方法。

1. 问题描述

给定一个链表，需要对该链表进行插入操作，最后顺序输出链表。

2. 代码实现

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 创建链表
ListNode* createLinkedList(int n) {
    ListNode* head = new ListNode(0);  // 创建一个虚拟头节点
    ListNode* cur = head;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        ListNode* newNode = new ListNode(val);
        cur->next = newNode;
        cur = cur->next;
    }
    return head->next;
}

// 插入结点
void insertNode(ListNode* head, int x, int y) {
    ListNode* cur = head;
    int index = 1;
    while (cur && index < x) {
        cur = cur->next;
        index++;
    }
    if (cur) {
        ListNode* newNode = new ListNode(y);
        newNode->next = cur->next;
        cur->next = newNode;
    }
}

// 打印链表
void printLinkedList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        cout << cur->val << ' ';
        cur = cur->next;
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    ListNode* head = createLinkedList(n);
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        insertNode(head, x, y);
    }
    printLinkedList(head);
    return 0;
}

3. 代码解释

ListNode 结构体：定义链表的结点结构，包含结点值 val 和指向下一个结点的指针 next。
createLinkedList 函数：创建链表，接收链表长度 n 作为参数，并从标准输入读取 n 个结点的值，构建链表并返回链表头结点。
insertNode 函数：插入结点，接收链表头结点 head、插入位置 x 和插入结点值 y 作为参数，将值 y 的新结点插入到第 x 个结点后面。
printLinkedList 函数：打印链表，接收链表头结点 head 作为参数，遍历链表并输出所有结点的值。
main 函数：主函数，从标准输入读取链表长度、插入结点数量以及插入位置和结点值，调用 createLinkedList 函数创建链表，调用 insertNode 函数插入结点，调用 printLinkedList 函数打印最终的链表。

4. 代码优化

使用虚拟头节点：在 createLinkedList 函数中创建了一个虚拟头节点，简化了插入操作，避免了特殊情况的处理。
使用循环遍历：在 insertNode 函数中使用循环遍历链表，找到插入位置，提高了代码的可读性和效率。
清晰的注释：代码中添加了清晰的注释，方便理解代码逻辑和功能。

5. 总结

本文详细介绍了使用 C++ 实现链表插入操作的代码，并对代码进行了优化，使之更易于理解和维护。希望本文能够帮助您快速掌握链表插入操作的实现方法。

注意：

链表插入操作需要保证插入位置的合法性，即插入位置不能小于 1，也不能大于链表长度。
链表插入操作需要使用 new 操作符动态分配内存，在使用完后需要使用 delete 操作符释放内存，防止内存泄漏。

代码测试：

输入：

输出：

5 4 8 2 7 3 1

6. 拓展

除了插入操作，链表还有其他操作，例如删除、查找、排序等。
链表可以用于实现各种数据结构和算法，例如栈、队列、图等。
链表是一种重要的数据结构，需要掌握其基本操作和应用场景。