已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。

算法思路：

1. 找到第一个大于等于x的结点p，p的前驱结点为pre。

2. 从p开始遍历链表，如果某个结点的值大于等于y，遍历结束。

3. 如果某个结点的值大于x且小于y，删除该结点，释放空间，继续遍历。

4. 如果某个结点的值小于x，将pre指向当前结点，继续遍历。

算法实现：

void removeRange(LinkList &L, int x, int y) {
    LNode *p = L->next, *pre = L;
    while (p && p->data < x) {  // 找到第一个大于等于x的结点p
        pre = p;
        p = p->next;
    }
    while (p && p->data < y) {  // 遍历链表
        if (p->data > x) {  // 删除大于x小于y的结点
            pre->next = p->next;
            free(p);
            p = pre->next;
        } else {  // 小于x的结点，pre指向当前结点
            pre = p;
            p = p->next;
        }
    }
}

时间复杂度：O(n)，其中n为链表长度。

相关问题

已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间

可以使用双指针来实现该算法。
1. 先找到第一个大于等于x的节点p，并记录其前驱节点pre。
2. 从p开始遍历链表，将符合条件的节点进行删除。直到遍历到第一个大于等于y的节点或链表结束。
3. 在删除符合条件的节点的同时，需要释放其占用的空间，并及时维护指针关系。
4. 最后返回链表的头节点，完成算法实现。

下面是算法实现的（C语言）代码：

typedef struct Node{
int val; // 元素值
struct Node* next; // 指向下一个节点的指针
} ListNode;

ListNode* deleteInRange(ListNode* head, int x, int y){
// 找到第一个大于等于x的节点并记录其前驱节点pre
ListNode* pre = NULL;
ListNode* p = head;
while(p && p->val < x){
pre = p;
p = p->next;
}

// 遍历链表删除符合条件的节点
while(p && p->val < y){
ListNode* q = p;
p = p->next;
// 释放空间
free(q);
}
// 维护指针关系
if(pre){
pre->next = p;
return head;
}else{
return p;
}
}

// 调用示例
ListNode* head = NULL;
head = deleteInRange(head, 3, 7);

已知线性表中的元素以值递增有序排列，并以单链表3作存储结构。试写一算法，删除表中所有值大于 mink 且小于 maxk 的元素，同时释放被删结点空间

算法思路：

遍历整个链表，找到值大于 mink 且小于 maxk 的结点，将其删除。

删除结点时需要注意：

- 删除头结点时，需要将头指针指向下一个结点。
- 删除非头结点时，需要将前一个结点的指针指向当前结点的下一个结点。

同时，需要释放删除结点的空间。

算法实现：

void deleteRange(LinkList &L, int mink, int maxk) {
    LNode *p = L->next;  // 指向第一个结点
    LNode *pre = L;      // 指向第一个结点的前一个结点
    while (p != NULL) {
        if (p->data > mink && p->data < maxk) {
            pre->next = p->next;  // 删除结点
            free(p);              // 释放空间
            p = pre->next;        // 指向下一个结点
        } else {
            pre = p;   // 指向下一个结点
            p = p->next;
        }
    }
}

注意：以上代码中，假设头结点的值为 -1。