去掉单链表中的数值相同的元素

问题描述：

在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如(7, 10, 10, 21, 30, 42, 42, 42, 51, 70)将变作(7, 10, 21, 30, 42, 51, 70)。

问题解答：

算法思想：由于是有序表，所有相同值域的结点都是相邻的。用p扫描递增单链表L，若*p结点的值域等于其后继结点的值域，则删除后者，否则p移向下一个结点。

void Del_Same(LinkList &L) {
    //L是递增有序的单链表，本算法删除表中数值相同的元素
    LNode *p=L->next, *q;    //p 为扫描工作指针
    while (p->next!=NULL) {
        q=p->next;  //q指向 *p 的后继结点
        if (p->data==q->data) {  //找到重复值的结点
            p->next=q->next; //释放*q 结点
            free(q);  //释放相同元素值的结点
        }else
            p = p->next;
    }
}

本算法的时间复杂度为O(n)，空间复杂度为O(1)。