设计一个算法,对一个有序的单链表,删除所有值大于x而不大于y的结点。(C语言)
时间: 2024-10-13 10:17:39 浏览: 35
设计一个C语言的算法,可以对有序的单链表删除所有值大于x且小于等于y的节点。以下是步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 创建新链表节点
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 助手函数:判断链表是否为空
int isEmpty(ListNode* head) {
return head == NULL;
}
// 助手函数:找到插入位置并删除节点
void deleteNodes(ListNode** head, int x, int y) {
ListNode* current = *head;
ListNode* prev = NULL;
while (current != NULL && current->val > x) {
if (current->val <= y) {
// 如果当前节点值在范围内,更新prev和current指针
if (prev == NULL) {
*head = current->next;
} else {
prev->next = current->next;
}
free(current); // 释放已删除节点
current = (*head); // 更新current指向下一个节点
} else {
prev = current; // 保持在范围外继续搜索
current = current->next;
}
}
}
// 打印链表
void printList(ListNode* head) {
while (head != NULL) {
printf("%d -> ", head->val);
head = head->next;
}
printf("NULL\n");
}
int main() {
// 初始化示例链表
ListNode* list = createNode(1);
list->next = createNode(2);
list->next->next = createNode(3);
list->next->next->next = createNode(4);
list->next->next->next->next = createNode(5);
int x = 3, y = 4;
deleteNodes(&list, x, y);
printf("Modified List: ");
printList(list);
return 0;
}
```
这个算法会遍历链表,如果遇到的节点值大于x并且小于等于y,则将其从链表中移除。当遍历结束后,原始链表就被修改为只包含值在[x, y]范围内的节点。
阅读全文