6-6 单链表结点删除
时间: 2024-03-25 10:35:31 浏览: 27
单链表结点删除的基本思路如下:
1. 找到待删除结点的前一个结点,记为prev。
2. 将prev结点的next指针指向待删除结点的下一个结点,跳过待删除结点。
3. 释放待删除结点的内存空间。
下面是单链表结点删除的具体实现代码:
```c++
void deleteNode(ListNode* head, int val) {
ListNode* prev = head;
ListNode* curr = head->next;
while (curr != NULL) {
if (curr->val == val) {
prev->next = curr->next;
delete curr;
return;
}
prev = curr;
curr = curr->next;
}
}
```
其中,head表示单链表的头结点,val表示待删除的结点的值。在函数中,我们先设置prev为头结点,curr为头结点的下一个结点,然后遍历单链表,查找待删除结点。如果找到了,就将prev的next指针指向curr的下一个结点,然后释放curr结点的内存空间即可。
相关问题
6-10 单链表结点删除
单链表结点删除的基本思路是找到要删除的结点的前一个结点,然后将它的 next 指针指向要删除结点的下一个结点。
具体操作步骤如下:
1. 找到要删除的结点的前一个结点,假设为 preNode。
2. 将 preNode 的 next 指针指向要删除结点的下一个结点,假设为 delNode。
3. 释放要删除的结点 delNode。
以下是 C++ 代码示例:
```cpp
void deleteNode(ListNode* head, int val) {
ListNode* preNode = head;
ListNode* delNode = head->next;
while (delNode != nullptr && delNode->val != val) {
preNode = delNode;
delNode = delNode->next;
}
if (delNode != nullptr) {
preNode->next = delNode->next;
delete delNode;
}
}
```
以上代码中,我们假设头结点为 head,要删除的结点的值为 val。首先从头结点开始遍历链表,找到要删除的结点的前一个结点 preNode 和要删除的结点 delNode。然后将 preNode 的 next 指针指向 delNode 的下一个结点,最后释放 delNode 的内存空间。
6-2 单链表基本运算算法的实现
单链表是一种常用的数据结构,它由若干个结点组成,每个结点包含一个数据域和一个指向下一个结点的指针。单链表的基本操作包括:初始化、插入结点、删除结点、查找结点等。下面是单链表基本运算算法的实现。
首先,定义单链表的结点结构体:
```c
typedef struct LNode {
DataType data;
struct LNode *next;
} LNode, *LinkList;
```
其中,`DataType`为数据类型,可以根据实际需求进行定义。
初始化单链表:
```c
void InitList(LinkList *L) {
*L = (LinkList) malloc(sizeof(LNode));
(*L)->next = NULL;
}
```
插入结点:
```c
void InsertList(LinkList L, int pos, DataType x) {
int index = 0;
LinkList p = L, q;
while (p && index < pos - 1) {
p = p->next;
index++;
}
if (!p || index > pos - 1) {
printf("Invalid position.\n");
return;
}
q = (LinkList) malloc(sizeof(LNode));
q->data = x;
q->next = p->next;
p->next = q;
}
```
删除结点:
```c
void DeleteList(LinkList L, int pos) {
int index = 0;
LinkList p = L, q;
while (p->next && index < pos - 1) {
p = p->next;
index++;
}
if (!p->next || index > pos - 1) {
printf("Invalid position.\n");
return;
}
q = p->next;
p->next = q->next;
free(q);
}
```
查找结点:
```c
LinkList FindList(LinkList L, DataType x) {
LinkList p = L->next;
while (p != NULL && p->data != x) {
p = p->next;
}
return p;
}
```
需要注意的是,在插入和删除结点时,需要保证传入的位置参数`pos`合法,即在链表的范围之内。此外,当查找结点时,如果找到了指定的元素,则返回它所在的结点的指针;如果没有找到,则返回`NULL`。
完整代码如下: