不使用额外空间,将 A,B两链表的元素交叉归并

设有两个按元素递增有序的单链表A和B,编一程序将A和B表归并成一个新的递增有序的单链表C，不使用额外空间。

#include<iostream>
usingnamespacestd;

structNode{
intm_Data;
Node*m_pNext;
};

Node*mergeLists(Node*pListA,Node*pListB)
{
if(pListA==NULL){
returnpListB;
}
elseif(pListB==NULL){
returnpListA;
}
else{
Node*pHead=NULL;
if(pListA->m_Data<pListB->m_Data){
pHead=pListA;
pListA=pListA->m_pNext;
}
else{
pHead=pListB;
pListB=pListB->m_pNext;
}

Node*pNode=pHead;
while(pListA&&pListB){
if(pListA->m_Data<pListB->m_Data){
pNode->m_pNext=pListA;
pListA=pListA->m_pNext;
}
else{
pNode->m_pNext=pListB;
pListB=pListB->m_pNext;
}
pNode=pNode->m_pNext;
}

if(pListA){
while(pListA){
pNode->m_pNext=pListA;
pListA=pListA->m_pNext;
pNode=pNode->m_pNext;
}
}
elseif(pListB){
while(pListB){
pNode->m_pNext=pListB;
pListB=pListB->m_pNext;
pNode=pNode->m_pNext;
}
}

returnpHead;
}
}

voidprintList(Node*pHead)
{
boolbEmpty=true;

while(pHead){
bEmpty=false;
cout<<pHead->m_Data<<"->";
pHead=pHead->m_pNext;
}

if(!bEmpty){
cout<<"NULL"<<endl;
}
}

intmain()
{
NodenodeA5={4,NULL};
NodenodeA4={4,&nodeA5};
NodenodeA3={3,&nodeA4};
NodenodeA2={1,&nodeA3};
NodenodeA1={1,&nodeA2};
NodenodeA0={0,&nodeA1};
Node*pHeadA=&nodeA0;

NodenodeB5={5,NULL};
NodenodeB4={4,&nodeB5};
NodenodeB3={3,&nodeB4};
NodenodeB2={2,&nodeB3};
NodenodeB1={2,&nodeB2};
NodenodeB0={1,&nodeB1};
Node*pHeadB=&nodeB0;

cout<<"LinkedListA:"<<endl;
printList(pHeadA);

cout<<"LinkedListB:"<<endl;
printList(pHeadA);

Node*pHead=mergeLists(pHeadA,pHeadB);
cout<<"MergedListA+B:"<<endl;
printList(pHeadA);
}