Icoding题解 线性表 删除范围内结点

题干

链表 删除范围内结点

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

链表结点定义如下：

1
2
3
4
5
6
struct _lnklist{
    ElemType data;
    struct _lnklist *next;
};
typedef struct _lnklist Node;
typedef struct _lnklist *LinkList;

函数原型如下：
void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk)

其中L指向链表的头结点。

分析

  • 简要分析题干：
    一个链表中的元素以递增的顺序排列，删除大于mink和小于maxk的元素。

  • 应当注意的问题：

    1. 链表的结点的删除操作

  • 解题思路：
    遍历链表的每一个结点，若结点中的data大于mink和小于maxk，则对元素进行删除，时间复杂度显然为O(n)。
    这一题考察最基本的链表删除。

核心代码

一般来说，对链表进行删除操作，我们需要定义两个指针。
一个指针指向当前结点，另一个结点指向当前结点的前一个结点。
在进行删除操作时，我们要删除当前结点，就需要将前一个结点的next，指向要被删除的结点的下一个结点。

1
2
3
4
5
6
LinkList Prev = L;
LinkList Curr = L;

//如果是空链表，直接返回。
if ( L == NULL || L->next == NULL)
    return;

确认至少有一个带数据的结点以后，我们再将第一个结点的位置赋值给Curr。
然后开始对链表进行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Curr = Prev->next;
while (Curr) {
    if (Curr->data > mink && Curr->data < maxk) {
        //首先将当前结点的下一个结点的位置交给前一个结点
        Prev->next = Curr->next;
        //删除当前结点
        free(Curr);
        //至此删除完成，我们把Curr更新到下一个结点
        Curr = Prev->next;
    }
    else {
        //如果不需要删除当前结点，就进行正常的遍历
        //此处不再赘述遍历的基本操作
        Prev = Curr;
        Curr = Curr->next;
    }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void lnk_del_x2y(LinkList L, ElemType mink, ElemType maxk) {
    LinkList curr = L->next;
    LinkList prev = L;
    LinkList temp;
    int flag = 0;
    while (curr != NULL){
        flag = 0;
        if(curr->data > mink && curr->data < maxk){
            temp = curr;
            curr = curr->next;
            free(temp);
            prev->next = curr;
            flag = 1;
        }
        if (flag == 0)
        {
            prev = curr;
            curr = curr->next;
        }
    }
    
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。