试写一个算法,在带头结点的单链表L中删除所有的数据元素为x的结点
时间: 2024-03-23 08:38:37 浏览: 23
算法如下:
1. 遍历链表L,找到所有数据元素为x的结点p和其前驱结点pre。
2. 将pre的next指针指向p的next指针(即跳过p结点)。
3. 删除p结点。
4. 重复1、2、3直到所有数据元素为x的结点都被删除。
5. 返回修改后的链表L。
C++代码实现如下:
```c++
void deleteNode(ListNode* L, int x) {
ListNode* p = L->next;
ListNode* pre = L;
while (p != NULL) {
if (p->data == x) {
pre->next = p->next;
ListNode* tmp = p;
p = p->next;
delete tmp;
} else {
pre = p;
p = p->next;
}
}
}
```
相关问题
2、 试写一个算法,在带头结点的单链表L的元素x前插入一个结点y
算法如下:
输入:带头结点的单链表L,元素x,结点y
输出:在元素x前插入结点y的单链表L
1. 创建一个新结点p,将结点y的数据域赋值给p的数据域,将p的指针域指向空。
2. 从头结点开始遍历单链表L,寻找元素x所在的结点pre以及元素x所在的结点pos。
3. 如果找到了元素x所在的结点pos,则将pre的指针域指向新结点p,将新结点p的指针域指向pos。
4. 如果没有找到元素x所在的结点pos,则在链表末尾插入新结点p。
代码实现(C++):
```cpp
void insertNode(ListNode* L, int x, int y) {
ListNode* p = new ListNode(y); // 创建新结点p,赋值为y
ListNode* pre = L; // pre指向头结点
ListNode* pos = L->next; // pos指向首个元素结点
while (pos != NULL && pos->val != x) { // 寻找元素x所在的结点pre和pos
pre = pos;
pos = pos->next;
}
if (pos != NULL) { // 如果找到了元素x所在的结点pos
pre->next = p; // 将pre的指针域指向新结点p
p->next = pos; // 将新结点p的指针域指向pos
} else { // 如果没有找到元素x所在的结点pos
pre->next = p; // 在链表末尾插入新结点p
p->next = NULL;
}
}
```
2、 试写一个算法,在带头结点的单链表L的元素x前插入一个结点y
算法如下:
1. 创建一个新结点y,将y的数据域设置为x。
2. 遍历链表L,找到元素x所在的结点p和其前驱结点pre。
3. 将pre的next指针指向y,将y的next指针指向p。
4. 返回修改后的链表L。
C++代码实现如下:
```c++
void insertNode(ListNode* L, int x, int y) {
ListNode* p = L->next;
ListNode* pre = L;
while (p != NULL && p->data != x) {
pre = p;
p = p->next;
}
ListNode* newNode = new ListNode(y);
pre->next = newNode;
newNode->next = p;
}
```