首页 > 试题广场 >

设 A 和 B 是两个单链表,其表中元素递增有序。试写一算法

[问答题]
设 A 和 B 是两个单链表,其表中元素递增有序。试写一算法将 A 和 B 归并成 一个按照元素值递减有序的单链表 C,并要求辅助空间的为 O(1),试分析算法的时间复杂度。
LinkList MergeSort (LinkList A, LinkList B) 
{
    //归并两个带有头结点的递增有序表,为一个带头结点的递减有序表。
    ListNode *pa,*pb,*q, *c;
    pa=A->next; //pa指向A表的开始结点
    c=A; c-next=NULL: //取A的头结点给c建立一个空的c表
    pb=B->next; //pb指向B的首元素结点
    free(B); // 回收B表的头结点空间
    
    
    while(pa&&pb)
    {
        if(pa->data <= pb->data){
            q=pa; pa=pa->next;
        }
        else {
            q=pb; pb=pb->next;
        }
        q->next=c->next; c->next=q;  // 把摘下的结点q作为首结点插入表C中(头插法)(为了C表的递减)
    }
    
    while (pa){  //如果pa表非空,则处理剩下的pa表
        q=pa; pa=pa->next;
        q->next=c->next; c->next=q;
    }
    while (pb){  //如果pb表非空,则处理剩下的pb表
        q=pb; pb=pb->next;
        q->next=c->next; c->next=q;
    }
    
    return c;
}


该算法的时间复杂度分析:
算法一共有三格while循环,其中第二个第三个只会执行一个。 
每个循环做的工作都是对链表中的结点进行扫描处理。
整个算法执行结束后,A和B表的每个结点都被处理了一遍。
所以设A表和B表的长度分别是m和n,则算法的时间复杂度是O(m+n).




发表于 2020-07-08 12:23:48 回复(0)