转载请注明出处：http://blog.csdn.net/ns_code/article/details/25739727
九度OJ上AC，採用归并的思想递归实现。
- 题目描写叙述：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们须要合成后的链表满足单调不减规则。
(hint: 请务必使用链表。)
- 输入：
输入可能包括多个測试例子，输入以EOF结束。
对于每一个測试案例，输入的第一行为两个整数n和m(0<=n<=1000, 0<=m<=1000)：n代表将要输入的第一个链表的元素的个数,m代表将要输入的第二个链表的元素的个数。
以下一行包括n个数t(1<=t<=1000000)：代表链表一中的元素。接下来一行包括m个元素，s(1<=t<=1000000)。
- 输出：
相应每一个測试案例，
若有结果，输出相应的链表。否则，输出NULL。
- 例子输入：
5 2 1 3 5 7 9 2 4 0 0
- 例子输出：
1 2 3 4 5 7 9 NULL
AC代码：
#include<stdio.h>
#include<stdlib.h>typedef int ElemType;typedef struct Node
{ElemType data;struct Node *next;
}Node,*pNode;/*
合并两个升序链表，合并后的链表依旧升序排列
*/
pNode MergeList(pNode pHead1,pNode pHead2)
{if(pHead1 == NULL)return pHead2;if(pHead2 == NULL)return pHead1;pNode pMergeHead = NULL;if(pHead1->data > pHead2->data){pMergeHead = pHead2;pMergeHead->next = MergeList(pHead1,pHead2->next);}else{pMergeHead = pHead1;pMergeHead->next = MergeList(pHead2,pHead1->next);}return pMergeHead;
}int main()
{int n,m;while(scanf("%d %d",&n,&m) != EOF){pNode pHead1 = NULL;if(n > 0){int i,data;scanf("%d",&data);pHead1 =(pNode)malloc(sizeof(Node));if(pHead1 == NULL)exit(EXIT_FAILURE);pHead1->data = data;pHead1->next = NULL;pNode pCur = pHead1;for(i=0;i<n-1;i++){scanf("%d",&data);pNode pNew =(pNode)malloc(sizeof(Node));if(pNew == NULL)exit(EXIT_FAILURE);pNew->data = data;pNew->next = NULL;pCur->next = pNew;pCur = pCur->next;}}pNode pHead2 = NULL;if(m > 0){int i,data;scanf("%d",&data);pHead2 =(pNode)malloc(sizeof(Node));if(pHead2 == NULL)exit(EXIT_FAILURE);pHead2->data = data;pHead2->next = NULL;pNode pCur = pHead2;for(i=0;i<m-1;i++){scanf("%d",&data);pNode pNew =(pNode)malloc(sizeof(Node));if(pNew == NULL)exit(EXIT_FAILURE);pNew->data = data;pNew->next = NULL;pCur->next = pNew;pCur = pCur->next;}}pNode pMergeHead = MergeList(pHead1,pHead2);if(pMergeHead == NULL)printf("NULL\n");else{pNode pCur = pMergeHead;while(pCur != NULL){//这里主要时要注意输出的格式if(pCur->next == NULL)printf("%d\n",pCur->data);elseprintf("%d ",pCur->data);pCur = pCur->next;}}}return 0;
}/************************************************************** Problem: 1519 User: mmc_maodun Language: C Result: Accepted Time:250 ms Memory:4080 kb****************************************************************/