链表合并（6）

我就是我 2022-06-09 10:13 151阅读 0赞

有两个递增排序的链表，把他们合并后的节点仍然是递增排序的。

这个问题的思路比较简单，首先比较p1，p2头结点，把较小的节点（比如是p1）赋值给mergeHead节点，然后，把p1->Next跟p2比较，以此类推，每次比较两个节点，所以这里可以考虑用递归。

#include <iostream>
    #include "ListCommon.h"
    
    using namespace std;
    
    ListNode* mergeList(ListNode* pHead1, ListNode* pHead2){
    	//健壮性处理
    	if(pHead1 == NULL){
    		return pHead2;
    	}else if(pHead2 == NULL){
    		return pHead1;
    	}
    	
    	ListNode* pMergeHead = NULL;
    	//递归处理两个节点
    	if(pHead1->m_nValue < pHead2->m_nValue){
    		pMergeHead = pHead1;
    		pMergeHead->m_pNext = mergeList(pHead1->m_pNext, pHead2);
    	}else{
    		pMergeHead = pHead2;
    		pMergeHead->m_pNext = mergeList(pHead2->m_pNext, pHead1);	
    	}
    	
    	return pMergeHead;
    }
    
    int main(int argc, char* argv[]){
    	ListNode* pHead1 = CreateListNode(1);
    	ListNode* pHead3 = CreateListNode(3);
    	ListNode* pHead5 = CreateListNode(5);
    	ListNode* pHead7 = CreateListNode(7);
            ConnectListNodes(pHead1, pHead3);
            ConnectListNodes(pHead3, pHead5);
            ConnectListNodes(pHead5, pHead7);
    	cout<<"list 1:"<<endl;
    	PrintList(pHead1);
    
    	ListNode* pHead2 = CreateListNode(2);
    	ListNode* pHead4 = CreateListNode(4);
    	ListNode* pHead6 = CreateListNode(6);
    	ListNode* pHead8 = CreateListNode(8);
            ConnectListNodes(pHead2, pHead4);
            ConnectListNodes(pHead4, pHead6);
            ConnectListNodes(pHead6, pHead8);
    	cout<<"list 2:"<<endl;
    	PrintList(pHead2);
    	
    	ListNode* pMHead = mergeList(pHead1,pHead2);
    	cout << "merged list :"<<endl;
    	PrintList(pMHead);
    	return 0;
    }

测试结果：

PC:~/algorithm$ g++ ListCommon.cpp MergeList.cpp -o MergeList  
PC:~/algorithm$ ./MergeList  
list 1:  
print list begin ---  
1  
3  
5  
7  
print list end  
list 2:  
print list begin ---  
2  
4  
6  
8  
print list end  
merged list :  
print list begin ---  
1  
2  
3  
4  
5  
6  
7  
8  
print list end