单链表的插入和删除
时间: 2023-11-05 07:04:17 浏览: 41
好的,我会为您详细解答。
单链表是一种链式存储结构,它由若干节点组成,每个节点包含数据域和指针域。其中,数据域存储节点的数据,指针域指向下一个节点的地址。
1. 插入节点
在单链表中插入一个节点,需要先找到插入位置的前一个节点,然后将新节点插入到该节点后面。
具体操作如下:
- 创建一个新节点,并为其分配内存空间;
- 将新节点的指针域指向插入位置的后继节点;
- 将插入位置的前驱节点的指针域指向新节点。
下面是一个示例代码:
```
// 定义节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 在单链表中插入节点
ListNode* insertNode(ListNode* head, int val, int pos) {
ListNode* newNode = new ListNode(val);
if (pos == 0) {
newNode->next = head;
return newNode;
}
ListNode* preNode = head;
for (int i = 0; i < pos - 1; i++) {
preNode = preNode->next;
}
newNode->next = preNode->next;
preNode->next = newNode;
return head;
}
```
2. 删除节点
在单链表中删除一个节点,需要先找到待删除节点的前一个节点,然后将前一个节点的指针域指向待删除节点的后继节点。
具体操作如下:
- 找到待删除节点的前驱节点;
- 将前驱节点的指针域指向待删除节点的后继节点;
- 释放待删除节点的内存空间。
下面是一个示例代码:
```
// 在单链表中删除节点
ListNode* deleteNode(ListNode* head, int val) {
ListNode* preNode = NULL;
ListNode* curNode = head;
while (curNode != NULL && curNode->val != val) {
preNode = curNode;
curNode = curNode->next;
}
if (curNode == NULL) {
return head;
}
if (preNode == NULL) {
head = curNode->next;
} else {
preNode->next = curNode->next;
}
delete curNode;
return head;
}
```
希望我的回答能够帮助您理解单链表的插入和删除操作。如果您有任何疑问,请随时向我提问。