设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素(mink和maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同 )。代码实现
时间: 2024-03-26 20:38:25 浏览: 112
因为链表是递增有序的,所以可以使用两个指针 prev 和 curr 分别指向链表的前一个节点和当前节点。初始时,prev 为 NULL,curr 为链表的头节点。然后依次遍历链表中的每个节点,如果当前节点的值大于等于 mink 且小于等于 maxk,就删除当前节点,即让前一个节点的 next 指针指向当前节点的下一个节点,释放当前节点的内存。否则,将 prev 指针指向当前节点,将 curr 指针指向下一个节点。遍历完成后,返回链表的头节点。
下面是算法的具体实现(C++ 代码):
```
ListNode* deleteRange(ListNode* head, int mink, int maxk) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
ListNode* curr = head;
while (curr != NULL) {
if (curr->val >= mink && curr->val <= maxk) {
prev->next = curr->next;
delete curr;
curr = prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
return dummy->next;
}
```
其中,ListNode 是链表节点的结构体,包含一个值 val 和一个指向下一个节点的指针 next。head 是链表的头节点指针。dummy 是一个虚拟节点,用于避免删除头节点时需要特殊处理。算法的时间复杂度为 O(n),其中 n 是链表的长度。
阅读全文