直接递归

代码：

#include <iostream>
#include <stack>
using namespace std;

 typedef struct listNode{
	int key;
	struct	listNode *pNext;
 } * pNode,Node;

void createNode(pNode &pHead){
		bool isFirst=true;
		int temp;
		scanf("%d",&temp);
		pNode p=pHead,q;
		while(temp!=0){
			q=(pNode)malloc(sizeof(Node));
			q->key=temp;
			q->pNext=NULL;
			if(isFirst){
				p=pHead=q;
				isFirst=false;
			}else{
				p->pNext=q;
				p=q;
			}

			scanf("%d",&temp);
		}
		cout<<"原链表是："<<endl;
		p=pHead;
		while(p){
			cout<<p->key<<" ";
			p=p->pNext;
		}
}
void print(const pNode merge){
	pNode p=merge;
	while(p){
		cout<<p->key<<" ";
		p=p->pNext;
	}
}
pNode merge(const pNode pHead1,const pNode pHead2){
	
	if(pHead1==NULL)
		return pHead2;
	else if(pHead2==NULL)
		return pHead1;
	pNode pMerge=NULL;
	if(pHead1->key > pHead2->key){
		pMerge = pHead2;	
    	pMerge->pNext = merge(pHead1,pHead2->pNext);
	}else{
		pMerge=pHead1;	
		pMerge->pNext=merge(pHead1->pNext,pHead2);
	}
	
	return pMerge;
}
void printListReverse(const pNode pHead){
	if(pHead==NULL)
		return;
	printListReverse(pHead->pNext);
	cout<<pHead->key;

}

int main(){
	pNode pHead1=NULL;
	pNode pHead2=NULL;

	createNode(pHead1);
	createNode(pHead2);
	pNode merge1 = merge(pHead1,pHead2);
	print(merge1);
	return 0;

}