单链表的创建,插入,删除,遍历代码
时间: 2023-05-22 14:05:01 浏览: 94
以下是单链表的创建、插入、删除和遍历的示例代码,供参考:
// 定义单链表节点结构体
struct ListNode {
int val; // 节点存储的值
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {}
};
// 创建单链表,返回指向链表节点的指针
ListNode* createLinkedList(vector<int> vals) {
ListNode *dummy = new ListNode(0); // 创建虚拟头节点
ListNode *cur = dummy; // 当前节点指针
for (int val : vals) {
cur->next = new ListNode(val); // 创建新节点
cur = cur->next; // 移动指针到新节点
}
return dummy->next; // 返回链表首节点指针
}
// 在指定位置插入节点,返回插入后的链表首节点指针
ListNode* insertNode(ListNode *head, int pos, int val) {
ListNode *dummy = new ListNode(0); // 创建虚拟头节点
dummy->next = head; // 将虚拟头节点连接到原链表首节点
ListNode *cur = dummy; // 当前节点指针
for (int i = 0; i < pos; i++) {
cur = cur->next; // 移动指针到插入位置之前的节点
if (cur == NULL) { // 如果链表长度小于 pos,则直接返回原链表
return head;
}
}
ListNode *newNode = new ListNode(val);
newNode->next = cur->next; // 将新节点连接到后面的节点
cur->next = newNode; // 将新节点连接到前面的节点
return dummy->next; // 返回链表首节点指针
}
// 删除指定节点,返回删除后的链表首节点指针
ListNode* deleteNode(ListNode *head, int val) {
ListNode *dummy = new ListNode(0); // 创建虚拟头节点
dummy->next = head; // 将虚拟头节点连接到原链表首节点
ListNode *cur = dummy; // 当前节点指针
while (cur->next) {
if (cur->next->val == val) { // 如果找到要删除的节点
ListNode *temp = cur->next; // 保存当前节点的下一个节点指针
cur->next = temp->next; // 将当前节点指向下下个节点
delete temp; // 释放被删除的节点内存
break;
}
cur = cur->next; // 移动指针到下一个节点
}
return dummy->next; // 返回链表首节点指针
}
// 遍历链表,输出节点值
void traverseList(ListNode *head) {
ListNode *cur = head;
while (cur) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
使用示例:
// 创建单链表
vector<int> vals = {1, 2, 3, 4, 5};
ListNode *head = createLinkedList(vals);
traverseList(head); // 输出 1 2 3 4 5
// 插入节点
head = insertNode(head, 3, 6);
traverseList(head); // 输出 1 2 3 6 4 5
// 删除节点
head = deleteNode(head, 2);
traverseList(head); // 输出 1 3 6 4 5