已知线性表中的元素按值递增有序排列，用带头结点的单链表L表示，现设计算法删除其中重复的多余元素并释放所占空间 typedef struct lnode { elemtp​​data; struct lnode​* next; } lnode, * linklist; void dessame ( linklist &L ) { ​}

可以使用双指针法来解决这个问题。具体步骤如下：

1. 定义两个指针p和q，初始时p指向头结点，q指向第一个结点。

2. 遍历链表，比较p和q结点的值是否相等，如果相等，则删除q结点并释放其空间；如果不相等，则将p指针指向q结点。

3. 遍历完链表后，将p指针指向NULL。

下面是具体实现：

void dessame (linklist &L) {
lnode *p = L->next;
while (p != NULL) {
lnode *q = p->next;
if (q != NULL && p->data == q->data) {
p->next = q->next;
delete q;
} else {
p = p->next;
}
}
L = p;
}

这个算法的时间复杂度是O(n)，其中n是链表中的元素个数。

相关问题

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

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

算法1：

1. 找到第一个值大于等于 mink 的结点 p，将其前驱结点记为 prev。
2. 从 p 开始遍历链表，找到第一个值大于 maxk 的结点 q，将其前驱结点记为 last。
3. 将 prev 的 next 指针指向 last 的 next 指针，释放 p 到 last 之间的所有结点空间。

示例代码：

void deleteRange1(LinkList L, ElemType mink, ElemType maxk) {
    Node *prev = L, *p = L->next;
    while (p != NULL && p->data < mink) {
        prev = p;
        p = p->next;
    }
    Node *last = p;
    while (last != NULL && last->data <= maxk) {
        last = last->next;
    }
    prev->next = last;
    while (p != last) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
}

算法2：

1. 创建一个新的头结点 newHead，并将其 next 指针指向原链表的头结点。
2. 找到第一个值大于等于 mink 的结点 p，将其前驱结点记为 prev。
3. 从 p 开始遍历链表，找到第一个值大于 maxk 的结点 q，将其前驱结点记为 last。
4. 将 prev 的 next 指针指向 last 的 next 指针，从 p 开始，释放被删结点空间。

示例代码：

void deleteRange2(LinkList L, ElemType mink, ElemType maxk) {
    Node *newHead = (Node*)malloc(sizeof(Node));
    newHead->next = L;
    Node *prev = newHead, *p = L;
    while (p != NULL && p->data < mink) {
        prev = p;
        p = p->next;
    }
    Node *last = p;
    while (last != NULL && last->data <= maxk) {
        last = last->next;
    }
    prev->next = last;
    while (p != last) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
    L = newHead->next;
    free(newHead);
}