C语言设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素(mink和maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)
时间: 2024-06-15 22:08:38 浏览: 144
数据结构与算法c++实现 删除顺序表中大于x的元素
5星 · 资源好评率100%
要设计一个算法来删除递增有序链表中值大于mink且小于maxk的所有元素,可以按照以下步骤进行:
1. 定义一个指针cur指向链表的头节点。
2. 定义两个指针prev和temp,分别指向cur的前一个节点和当前节点。
3. 遍历链表,直到cur为空为止。
4. 判断当前节点的值是否大于mink且小于maxk,如果是,则执行删除操作。
- 如果prev为空,说明要删除的节点是头节点,将头节点指向下一个节点。
- 如果prev不为空,将prev的next指针指向temp的next节点,即跳过当前节点。
5. 如果当前节点的值不满足删除条件,则更新prev和cur指针,继续遍历下一个节点。
6. 返回删除元素后的链表。
以下是C语言实现该算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
int val;
struct ListNode* next;
};
// 删除递增有序链表中值大于mink且小于maxk的所有元素
struct ListNode* deleteRange(struct ListNode* head, int mink, int maxk) {
struct ListNode dummy; // 创建一个虚拟头节点
dummy.next = head;
struct ListNode* prev = &dummy;
struct ListNode* cur = head;
while (cur != NULL) {
if (cur->val > mink && cur->val < maxk) {
prev->next = cur->next; // 删除当前节点
free(cur);
cur = prev->next;
} else {
prev = cur; cur = cur->next;
}
}
return dummy.next; // 返回删除元素后的链表
}
// 创建链表
struct ListNode* createList(int arr[], int n) {
struct ListNode* head = NULL;
struct ListNode* tail = NULL;
for (int i = 0; i < n; i++) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = arr[i];
newNode->next = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
return head;
}
// 打印链表
void printList(struct ListNode* head) {
struct ListNode* cur = head;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
struct ListNode* head = createList(arr, n);
printf("原始链表:");
printList(head);
int mink = 3;
int maxk = 7;
head = deleteRange(head, mink, maxk);
printf("删除后的链表:");
printList(head);
return 0;
}
```
阅读全文