已知有序表中的元素以值递增有序排列，并以带头结点的单链表作存储结构。 试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删除结点空间，并分析算法的时间复杂度。

算法思路：

1. 找到第一个值大于mink的结点p，记录其前驱结点pre；
2. 从p开始遍历链表，对于每个值大于mink且小于maxk的结点，删除并释放空间；
3. 遍历完后，将pre的next指针指向p的next结点即可。

算法实现：

void deleteRange(LinkList &L, int mink, int maxk) {
    ListNode *pre = L;
    ListNode *p = L->next;
    while (p != NULL && p->data <= mink) {
        pre = p;
        p = p->next;
    }
    while (p != NULL && p->data < maxk) {
        ListNode *q = p;
        p = p->next;
        pre->next = p;
        delete q;
    }
}

时间复杂度：O(n)，其中n为链表长度。因为只需要遍历链表一次即可删除所有符合条件的结点。

相关问题

python已知有序表中的元素以值递增有序排列，并以带头结点的单链表作存储结构。 试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删除结点空间，并分析算法的时间复杂度。

算法思路：

1. 找到第一个值大于mink的结点p，以及它的前驱结点pre；

2. 从p开始遍历链表，找到第一个值大于等于maxk的结点q，以及它的前驱结点pre_q；

3. 将pre的next指针指向q，释放p到pre_q之间的所有结点空间。

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

算法实现：

def delete_range(head, mink, maxk):
    p = head
    pre = None
    while p.next and p.next.val <= mink:
        pre = p
        p = p.next
    q = p.next
    pre_q = p
    while q and q.val < maxk:
        pre_q = q
        q = q.next
    pre.next = pre_q.next
    while p != q:
        temp = p
        p = p.next
        del temp

其中，链表结点类的定义为：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

测试代码：

def create_linked_list(nums):
    head = ListNode()
    p = head
    for num in nums:
        p.next = ListNode(num)
        p = p.next
    return head

def print_linked_list(head):
    p = head.next
    while p:
        print(p.val, end=' ')
        p = p.next
    print()

if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    mink, maxk = 3, 7
    head = create_linked_list(nums)
    print('原始链表：')
    print_linked_list(head)
    delete_range(head, mink, maxk)
    print('删除后的链表：')
    print_linked_list(head)

输出结果：

原始链表：
1 2 3 4 5 6 7 8 9 
删除后的链表：
1 2 8 9 

已知有序表中的元素以值递增有序排列，并以带头结点的单链表作存储结构。 试用python写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删除结点空间，并分析算法的时间复杂度

算法思路：

1. 找到第一个大于等于mink的结点p和它的前驱结点pre，同时记录pre的位置。

2. 从p开始遍历链表，找到第一个大于maxk的结点q，同时记录q的前驱结点。

3. 从pre开始遍历到q的前驱结点，依次释放这些结点的空间。

4. 将pre的next指针指向q，完成删除操作。

算法实现：

def delete_range(head, mink, maxk):
    pre = head
    while pre.next and pre.next.data < mink:
        pre = pre.next
    p = pre.next
    while p and p.data <= maxk:
        pre.next = p.next
        p = p.next
    while pre.next and pre.next.data <= maxk:
        pre.next = pre.next.next
    return head

时间复杂度分析：

该算法的时间复杂度为O(n)，其中n为链表的长度。因为只需要遍历一次链表，时间复杂度与链表长度成线性关系，因此算法的时间复杂度为O(n)。