## 問題描述 > 假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。試編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來的兩個單鏈表結點存放歸并后的單鏈表 ## 算法思想 > 分析本題可見，本題實際上就是一次有序歸并排序，因此我們借鑒歸并排序的思想來實習本算法。 這里圖個方便，就又新建了一個頭結點，導致本算法中同時出現了三個頭節點。 首先對兩條已知的單鏈表進行遍歷，每訪問一個結點，便對比較一次，哪個結點比較小，就將其取下然后采用頭插法建立單鏈表的方式重新建立單鏈表，形成元素值遞減的單鏈表。 ## 算法描述 ~~~ LinkList MergeList(LNode *head1, LNode *head2, LNode *head) { LNode *prep=head1; LNode *p=head1->next; LNode *preq=head2; LNode *q=head2->next; //查找較小值 while(p&&q){ if(p->data<q->data){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; }else{ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } } //若第一個單鏈表未遍歷完成，則繼續插入 while(p){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; } //若第二個單鏈表為遍歷完成，則繼續插入 while(q){ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } free(head1); free(head2); return head; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList MergeList(LNode*, LNode*, LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2=CreatList(head2); Print(head1); Print(head2); LNode *head; head=(LNode*)malloc(sizeof(LNode)); head=MergeList(head1, head2, head); Print(head); return 0; } //尾插法建立單鏈表 LinkList CreatList(LNode *head) { LNode *r=head; LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } r->next=NULL; return head; } //歸并單鏈表 LinkList MergeList(LNode *head1, LNode *head2, LNode *head) { LNode *prep=head1; LNode *p=head1->next; LNode *preq=head2; LNode *q=head2->next; while(p&&q){ if(p->data<q->data){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; }else{ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } } while(p){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; } while(q){ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } free(head1); free(head2); return head; } //打印全部結點 void Print(LNode* head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~