已知带头结点单链表中各结点的元素值为整形且递增有序，设计算法删除链表中所有大于mink且小于maxk的元素，并释放被删结点的空间。

算法思路：

使用两个指针p和q，p指向当前遍历的结点，q指向p的前驱结点。如果p的元素值大于mink且小于maxk，则删除p结点并释放其空间，同时更新q的next指向p的下一个结点，p指向q的下一个结点，继续遍历下一个结点。如果p的元素值不符合删除条件，则将p和q都向后移动一个结点。

算法实现：

void deleteRange(Node* head, int mink, int maxk) {
    Node *p = head->next, *q = head;
    while (p != NULL) {
        if (p->data > mink && p->data < maxk) {
            q->next = p->next;
            Node* tmp = p;
            p = p->next;
            delete tmp;
        } else {
            p = p->next;
            q = q->next;
        }
    }
}

算法分析：

时间复杂度为O(n)，空间复杂度为O(1)。该算法使用了两个指针p和q，分别指向当前遍历的结点和其前驱结点，因此只需要一次遍历就可以完成删除操作。同时，该算法没有使用递归，因此空间复杂度为常数级别。

相关问题

已知带头结点单链表中各结点的元素值为整形且递增有序，设计算法删除链表中所有大于mink且小于maxk的元素，并释放被删结点的空间

1. 初始化指针p为头结点，q为p的后继结点。
2. 如果q非空，则执行以下操作：
a. 如果q的元素值大于mink且小于maxk，则将p的后继结点指向q的后继结点，释放q结点的空间；
b. 否则，将p指向q，q指向p的后继结点。
3. 返回头结点。

代码实现如下：

void deleteRange(Node* head, int mink, int maxk) {
    Node* p = head;
    Node* q = p->next;
    while (q != NULL) {
        if (q->data > mink && q->data < maxk) {
            p->next = q->next;
            free(q);
            q = p->next;
        } else {
            p = q;
            q = p->next;
        }
    }
}

已知线性表中的元素以值递增有序排列，并以单链表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。