【剑指Offer面试题】 九度OJ1519：合并两个排序的链表

【剑指Offer面试题】 九度OJ1519：合并两个排序的链表

题目链接地址：
.php?pid=1519

题目1519：合并两个排序的链表

时间限制：1 秒内存限制：128 兆特殊判题：否提交：1677解决：767
题目描述：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
(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

思路分析：

平时我经常见到合并链表的题目，考察大家的分析问题能力，编程基本功和鲁棒性。
我们需要注意的地方：

1. 检查指针是否指向NULL。确保不发生内存错误。
2. 合并链表要把原链表的节点拼成一条，而不是构造出一个新的链表。
   如果这两个没有注意到，估计会被面试官鄙视。
   时间复杂度O(m + n)
   空间复杂度O(1)

代码：

改良了之前的代码，函数化。注意createLinklist(LNode* &pHead,int len) 里的参数，因为pHead新建了单链表，需要引用，不然出了函数就失效。

/********************************* 
【剑指Offer面试题】 九度OJ1519：合并两个排序的链表
Author:牧之丶  Date：2015年
Email:bzhou84@163 
**********************************/
#include<stdio.h>
#include<stdlib.h>  
#include<string>
#include <math.h>
#include<stack>
#include <vector>
#include <iostream>
using namespace std;typedef int ElemType;  
typedef struct Node
{ElemType data;struct Node *pNext;
}LNode;/** 
* 构造长度为len的单链表 
* @param len  链表中的元素个数 
* @return head  返回单链表的头指针 
*/ 
void createLinklist(LNode* &pHead,int len)  
{  if (len>0){int i,data;scanf("%d",&data);pHead =(LNode*)malloc(sizeof(LNode));   //不带头结点建单链表if(pHead == NULL)           exit(EXIT_FAILURE);pHead->data = data;pHead->pNext = NULL;LNode* pCur = pHead;for(i=0;i<len-1;i++){scanf("%d",&data);LNode*  pNew =(LNode* )malloc(sizeof(LNode));if(pNew == NULL)exit(EXIT_FAILURE);pNew->data = data;pNew->pNext = NULL;pCur->pNext = pNew;pCur = pCur->pNext;}}
}  
/* 
合并两个升序链表，合并后的链表依然升序排列 
*/ 
LNode* Merge(LNode* pHead1,LNode* pHead2)  
{  if(pHead1 == NULL)  return pHead2;  if(pHead2 == NULL)  return pHead1;  LNode* pMergeHead = NULL;  if(pHead1->data < pHead2->data)  {  pMergeHead = pHead1;  pMergeHead->pNext = Merge(pHead1->pNext,pHead2);  }  else {  pMergeHead = pHead2;  pMergeHead->pNext = Merge(pHead1,pHead2->pNext);  }  return pMergeHead;  
}  
/** 
* 打印单链表 
* @param head  被打印链表的头指针 
* @return void 
*/ 
void printLinklist(LNode * pNewHead)  
{  if(pNewHead == NULL)printf("NULLn");else{  LNode* pCur = pNewHead;  while(pCur != NULL)  {  //这里主要时要注意输出的格式  if(pCur->pNext == NULL)  printf("%dn",pCur->data);  else printf("%d ",pCur->data);  pCur = pCur->pNext;  }  } 
}  int main()
{int n,m;while(scanf("%d %d",&n,&m) != EOF){LNode* pHead1=NULL;LNode* pHead2=NULL;createLinklist(pHead1,n);createLinklist(pHead2,m);LNode* pNewHead = Merge(pHead1,pHead2);printLinklist(pNewHead);}return 0;
}/**************************************************************Problem: 1519Language: C++Result: AcceptedTime:240 msMemory:4688 kb
****************************************************************/

总结

• 检查指针是否指向NULL。
• 函数参数的引用
• 合并链表要把原链表的节点拼成一条，而不是构造出一个新的链表。