设链表中的元素以递增序存储,用类C语言设计高效算法删除其中大于等于mink且小于等于maxk的元素
时间: 2023-05-25 14:04:11 浏览: 59
链表中的元素以递增序存储,可以采用双指针法,分别从链表头开始遍历,当遇到第一个大于等于mink的元素时,记录下该节点,并继续遍历。当遇到第一个大于maxk的元素时,就可以退出遍历了。然后将记录下的节点之后的链表全部删除即可。
具体实现如下:
```
void deleteRange(node** head, int mink, int maxk) {
node* cur = *head;
node* prev = NULL;
node* delStart = NULL;
while (cur != NULL && cur->data < mink) {
prev = cur;
cur = cur->next;
}
delStart = prev;
while (cur != NULL && cur->data <= maxk) {
prev = cur;
cur = cur->next;
}
if (delStart == NULL) {
*head = cur;
} else {
delStart->next = cur;
}
while (prev != NULL && prev->next != cur) {
node* delNode = prev->next;
prev->next = delNode->next;
free(delNode);
}
}
```
该算法的时间复杂度为O(n),其中n为链表中元素的个数。