线性表算法题目解答

题目1 - 将2个递增的有序链表合并为一个有序链表;要求结果链表仍然使用两个链表的存储空间,不另外占用其他的存储空间. 表中不允许有重复的数据

void MergeList(LinkList *list1, LinkList *list2, LinkList *list3) {
    
    LinkList p1,p2,p3,tmp;
    p1 = (*list1)->next;
    p2 = (*list2)->next;
    
    *list3 = p3 = *list1;
    while (p1 && p2) {
        printf("%d %d\n",p1->data,p2->data);
        if (p1->data == p2->data) {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
            
            tmp = p2->next;
            free(p2);
            p2 = tmp;
        } else if(p1->data > p2->data) {
            p3->next = p2;
            p2 = p2->next;
            p3 = p2;
        } else {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        }
    }
    
//    if (NULL == p1) {
//        p3->next = p2;
//    } else if (NULL == p2) {
//        p3->next = p1;
//    }
    p3->next = p1 ? p1 : p2;
    
    free(*list2);
}

题目2 - 已知两个链表A和B分别表示两个集合.其元素递增排列. 设计一个算法,用于求出A与B的交集,并存储在A链表中; 例如: La = {2,4,6,8}; Lb = {4,6,8,10}; Lc = {4,6,8}

void Intersection(LinkList *list1, LinkList *list2, LinkList *list3) {
    LinkList p1,p2,p3,tmp;
    p1 = (*list1)->next;
    p2 = (*list2)->next;
    *list3 = p3 = *list1;
    
    while (p1 && p2) {
        if (p1->data == p2->data) {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
            tmp = p2->next;
            free(p2);
            p2 = tmp;
        } else if (p1->data > p2->data) {
            tmp = p2->next;
            free(p2);
            p2 = tmp;
        } else {
            tmp = p1->next;
            free(p1);
            p1 = tmp;
        }
    }
    p3->next = NULL;
    
    if (NULL == p1) {
        while (p2) {
            tmp = p2->next;
            free(p2);
            p2 = tmp;
        }
    }
    
    if (NULL == p2) {
        while (p1) {
            tmp = p1->next;
            free(p1);
            p1 = tmp;
        }
    }
    
    free(*list2);
}

题目3 - 设计一个算法,将链表中所有节点的链接方向"原地旋转",即要求仅仅利用原表的存储空间. 换句话说,要求算法空间复杂度为O(1); 例如:L={0,2,4,6,8,10}, 逆转后: L = {10,8,6,4,2,0};

void Inverse(LinkList *list) {
    LinkList p,rear;
    p = (*list)->next;
    (*list)->next = NULL;
    
    while (p) {
        rear = p->next;
        p->next = (*list)->next;
        (*list)->next = p;
        p = rear;
    }
}

题目4 - 设计一个算法,删除递增有序链表中值大于等于mink且小于等于maxk(mink,maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)的所有元素;

void DeleteMinMax(LinkList *list, int mink, int maxk) {
    LinkList p,q,pre,tmp;
    pre = (*list);
    p = (*list)->next;
    while (p && p->data < mink) {
        pre = p;
        p = p->next;
    }
    
    while (p && p->data <= maxk) {
        p = p->next;
    }
    
    q = pre->next;
    pre->next = p;
    
    while (q != p) {
        tmp = q->next;
        free(q);
        q = tmp;
    }
    
}

题目5 - 设将n(n>1)个整数存放到一维数组R中, 试设计一个在时间和空间两方面都尽可能高效的算法;将R中保存的序列循环左移p个位置(0<p<n)个位置, 即将R中的数据由(x0,x1,......,xn-1)变换为(xp,xp+1,...,xn-1,x0,x1,...,xp-1).

例如: pre[10] = {0,1,2,3,4,5,6,7,8,9},
n = 10,p = 3;
pre[10] = {3,4,5,6,7,8,9,0,1,2}

void Reverse(int *p, int left, int right) {
    int i = left;
    int j =  right;
    int tmp;
    while (i < j) {
        tmp = p[i];
        p[i] = p[j];
        p[j] = tmp;
        i++;
        j--;
    }
}

void Shift(int *p,int n,int position) {
    if (position > 0 && position < n) {
        Reverse(p, 0, n - 1);
        Reverse(p, 0, n - position -1);
        Reverse(p, n-position, n-1);
    }
}

题目6 - 已知一个整数序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...= apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主元素; 若B = (0,5,5,3,5,1,5,7),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.

int MainElement(int *A, int n) {
    int count = 1;
    int key = A[0];
    for (int i = 1; i < n; i++) {
        if (key == A[i]) {
            count++;
        } else {
            if (count > 0) {
                count--;
            } else {
                key = A[i];
                count = 1;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (key == A[i]) {
            count++;
        }
    }
    
    if (count > n/2) {
        return key;
    }
    return -1;
}

题目7 - 用单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计一个时间复杂度尽可能高效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第一次出现的结点,而删除其余绝对值相等的结点.例如,链表A = {21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};

void DeleteEqualNode(LinkList *list, int n) {
    int *a = alloca(sizeof(int) * n);
    LinkList rear = *list;
    for (int i = 0; i < n; i++) {
        *(a+i) = 0;
    }
    LinkList p = (*list)->next;
    while (p) {
        if (a[abs(p->data)] == 1) {
            rear->next = p->next;
            free(p);
            p = rear->next;
        } else {
            a[abs(p->data)] = 1;
            rear = p;
            p = p->next;
        }
    }
}