设已知线性表中的元素(整数)以值递增有序排列,并以单链表作为存储结构。请用C语言写一个高效算法,删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素),分析算法的时间复杂度(注意,mink)
时间: 2024-01-22 18:21:39 浏览: 157
算法步骤如下:
1. 找到第一个大于等于mink的元素的前驱结点p和最后一个小于等于maxk的元素的后继结点q;
2. 从p开始遍历链表,删除所有值大于mink且小于maxk的元素,直到当前结点为q为止。
代码实现如下:
```c
void deleteRange(ListNode* head, int mink, int maxk) {
ListNode *p = head, *pre = NULL;
while (p != NULL && p->val < mink) { // 找到第一个大于等于mink的元素的前驱结点p
pre = p;
p = p->next;
}
ListNode *q = p;
while (q != NULL && q->val <= maxk) { // 找到最后一个小于等于maxk的元素的后继结点q
q = q->next;
}
if (pre == NULL) { // 如果p是头结点,则需要修改头结点
head = q;
} else { // 否则,将p的前驱结点pre的next指向q
pre->next = q;
}
while (p != q) { // 从p开始遍历链表,删除所有值大于mink且小于maxk的元素
ListNode *tmp = p->next;
free(p);
p = tmp;
}
}
```
时间复杂度分析:
该算法的时间复杂度为O(n),其中n为链表的长度。因为只需要遍历一次链表,找到第一个大于等于mink的元素的前驱结点p和最后一个小于等于maxk的元素的后继结点q,然后再从p开始遍历链表,删除所有值大于mink且小于maxk的元素,直到当前结点为q为止。因此,该算法的时间复杂度是O(n)。