C++单链表操作：头插尾插与遍历

在数据结构中，链表是一种常见的基础数据结构，以其动态存储分配、插入和删除操作的高效率等特性，在C++等编程语言中广泛使用。本资源涉及到的单链表是一个由节点组成的线性集合，每个节点包含数据部分和指向下一个节点的指针。单链表节点的数据结构通常可以定义如下： ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ``` 在本资源中，描述了C++环境下单链表的几种基本操作和遍历方法，具体包括头插法、尾插法、前序遍历、中序遍历、后序遍历以及插入和删除操作。 1. **头插法**：是一种在链表头部插入新节点的方法。每次插入时，新节点都会成为链表的第一个元素。头插法的实现可以保证插入操作的时间复杂度为O(1)。具体的实现步骤为：创建一个新节点，将其next指针指向当前链表的头节点，然后更新链表头指针为新节点。代码示例如下： ```cpp ListNode* headInsert(ListNode* head, int val) { ListNode* newNode = new ListNode(val); newNode->next = head; return newNode; } ``` 2. **尾插法**：是在链表尾部插入新节点的方法。为了使用尾插法，通常需要一个指向链表尾部的指针（尾指针）。当新节点插入时，尾指针指向的新节点会成为链表的新尾部，并且尾指针自身更新为指向该新节点。尾插法的代码实现如下： ```cpp void tailInsert(ListNode*& tail, int val) { ListNode* newNode = new ListNode(val); tail->next = newNode; tail = newNode; } ``` 3. **遍历**：链表的遍历包括前序遍历、中序遍历和后序遍历。这些遍历方法原本用于树形结构，在链表中仅需按顺序访问每个节点即可。 - **前序遍历**：访问节点 -> 遍历左子树 -> 遍历右子树 - **中序遍历**：遍历左子树 -> 访问节点 -> 遍历右子树 - **后序遍历**：遍历左子树 -> 遍历右子树 -> 访问节点 由于链表不具有子树的概念，遍历通常表示为“先访问链表的第一个节点，然后递归地遍历剩余的链表”。单链表的遍历实现可以如下： ```cpp void traverse(ListNode* node) { if (node == nullptr) return; // 处理当前节点 traverse(node->next); } ``` 4. **插入操作**：在单链表的任意位置插入一个新节点，需要三个指针：一个指向前一个节点，一个指向当前节点，一个指向下一个节点。插入步骤通常是：改变前一个节点的next指针，使其指向新节点；将当前节点的next指针指向新节点；最后，如果需要，还需要更新新节点的next指针。代码实现如下： ```cpp void insertNode(ListNode*& head, int pos, int val) { ListNode* newNode = new ListNode(val); if (pos == 0) { newNode->next = head; head = newNode; return; } ListNode* prev = head; for (int i = 0; prev != nullptr && i < pos - 1; ++i) { prev = prev->next; } if (prev == nullptr) return; // 超出链表长度，无法插入 newNode->next = prev->next; prev->next = newNode; } ``` 5. **删除操作**：删除链表中的某个节点，需要确定要删除节点的前一个节点，然后改变其next指针，使其指向要删除节点的下一个节点。之后释放要删除节点的内存。代码实现如下： ```cpp void deleteNode(ListNode*& head, int pos) { if (head == nullptr || pos < 0) return; ListNode* temp = head; if (pos == 0) { head = head->next; delete temp; return; } for (int i = 0; temp != nullptr && i < pos - 1; ++i) { temp = temp->next; } if (temp == nullptr || temp->next == nullptr) return; ListNode* next = temp->next->next; delete temp->next; temp->next = next; } ``` 以上是对标题和描述中提到的单链表基本操作的知识点介绍。通过对这些操作的掌握，可以实现对单链表数据结构的有效管理和使用。这些操作在实际编程中非常重要，特别是在处理无法预测大小变化的数据集合时。