本文共 2842 字,大约阅读时间需要 9 分钟。
地址:http://ac.jobdu.com/problem.php?pid=1519
题目1519:合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
(hint: 请务必使用链表。)
输入可能包含多个测试样例,输入以EOF结束。
对于每个测试案例,输入的第一行为两个整数n和m(0<=n<=1000, 0<=m<=1000):n代表将要输入的第一个链表的元素的个数,m代表将要输入的第二个链表的元素的个数。 下面一行包括n个数t(1<=t<=1000000):代表链表一中的元素。接下来一行包含m个元素,s(1<=t<=1000000)。
对应每个测试案例,
若有结果,输出相应的链表。否则,输出NULL。
5 21 3 5 7 92 40 0
1 2 3 4 5 7 9NULL
依次比较两个链表的头节点,小的节点就取出。
注意:
1、两个链表都为空
2、其中一个链表为空
#include#include struct listNode { int data; listNode *next;};listNode *merge(listNode* p, listNode *q) { if(p == NULL && q == NULL){ return NULL; } listNode *little = NULL; listNode *tail = NULL; listNode *head = NULL; bool first = true; while(p != NULL && q != NULL) { if(p->data <= q->data) { little = p; p = p->next; } else { little = q; q = q->next; } if(first) { head = little; tail = little; first = false; } else { tail->next = little; tail = tail->next; } } if(p != NULL) { if(tail != NULL) tail->next = p; else head = p; } else if(q != NULL) { if(tail != NULL) tail->next = q; else head = q; } return head;}int main(){ int n, m; while(scanf("%d %d", &n, &m) != EOF) { listNode *list1 = NULL; listNode *list2 = NULL; listNode *p = NULL; listNode *q = NULL; for(int i = 0; i < n; i ++) { p = (listNode *)malloc(sizeof(listNode)); scanf("%d", &p->data); p->next = NULL; if(i == 0) { list1 = p; q = p; } else { q->next = p; q = q->next; } } for(int i = 0; i < m; i ++) { p = (listNode *)malloc(sizeof(listNode)); scanf("%d", &p->data); p->next = NULL; if(i == 0) { list2 = p; q = p; } else { q->next = p; q = q->next; } } p = merge(list1, list2); if(p != NULL) { bool head = true; while(p != NULL) { if(head) { printf("%d", p->data); head = false; } else printf(" %d", p->data); p = p->next; } printf("\n"); } else printf("NULL\n"); } return 0;}/************************************************************** Problem: 1519 Language: C++ Result: Accepted Time:240 ms Memory:4188 kb****************************************************************/
转载地址:http://uesob.baihongyu.com/