6

題目

       用單連結清單儲存m個整數，結點結構為：[data][link]，且

（n為正整數），現要求設計一個時間複雜度盡可能高效的算法，對于連結清單中data的絕對值相等的結點，僅保留第一次出現的結點而删除其餘絕對值相等的結點。        例如，給定單連結清單如下

        則删除結點後的head為

分析

             1個足夠大的數組，儲存結點data絕對值出現的次數，思路和第5題是一樣的，從前到後周遊，如果第一次出現，删除結點

代碼

typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode *link;
}LNode, *LinkList;

void removeRepeat(LinkList &L, int n) {
    int *num = (int *)malloc(sizeof(int) * (n + 1));
    for(int i = 0; i < n + 1; i++) {
        *(num + i) = 0;
    }
    LNode *p = L, *q = L -> link;
    while(q) {
        int m = q -> data > 0 ? q -> data : -q -> data;
        *(num + m) = *(num + m) + 1;
        if(*(num + m) != 1) {
            p -> link = q -> link;
            free(q);
            q = p -> link;
        }else {
            p = p -> link;
            q = q -> link;
        }
    }
}
           

源代碼

           http://123.206.59.223:8080/code/code/6.rar