數據結構實驗之鏈表四：有序鏈表的歸并

Time Limit:?1000 ms?Memory Limit:?65536 KiB Submit?Statistic?Discuss

Problem Description

分別輸入兩個有序的整數序列（分別包含M和N個數據），建立兩個有序的單鏈表，將這兩個有序單鏈表合并成為一個大的有序單鏈表，并依次輸出合并后的單鏈表數據。

Input

第一行輸入M與N的值；?
第二行依次輸入M個有序的整數；
第三行依次輸入N個有序的整數。

Output

輸出合并后的單鏈表所包含的M+N個有序的整數。

Sample Input

6 5 1 23 26 45 66 99 14 21 28 50 100

Sample Output

1 14 21 23 26 28 45 50 66 99 100

Hint

不得使用數組！

拆開重建，連節點前先比較，找出較小的一個作為節點；

#include <stdio.h> #include <stdlib.h>struct node {int data;struct node *next; };int main() {struct node *head, *tail, *p, *q, *head2;head = (struct node *)malloc(sizeof(struct node));head->next = NULL;head2 = (struct node *)malloc(sizeof(struct node));head2->next = NULL;int i, m, n;scanf("%d %d",&m,&n);tail = head;for(i=0; i<m; i++){p = (struct node *)malloc(sizeof(struct node));scanf("%d",&p->data);p->next = NULL;tail->next = p;tail = p;}tail = head2;for(i=0; i<n; i++){p = (struct node *)malloc(sizeof(struct node));scanf("%d",&p->data);p->next = NULL;tail->next = p;tail = p;}p = head->next;q = head2->next;tail = head;while(p&&q){if(p->data<q->data){tail->next = p;tail = p;p = p->next;}else{tail->next = q;tail = q;q = q->next;}}while(p){tail->next = p;tail = p;p = p->next;}while(q){tail->next = q;tail = q;q = q->next;}p = head->next;while(p->next){printf("%d ",p->data);p = p->next;} printf("%d\n",p->data);return 0; }

轉載于:https://www.cnblogs.com/gaojinmanlookworld/p/10586985.html

總結

以上是生活随笔為你收集整理的SDUT OJ 数据结构实验之链表四：有序链表的归并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。