【C/C++练习题】合并两个排序的链表

《剑指Offer》面试题25：合并两个排序的链表

1 题目

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图3.11中的链表1和链表2，则合并之后的升序链表如链表3所示。

2 分析

递归思想，每次递归过程，将两个待合并链表的首节点中选出一个节点（作为合并之后的链表首节点），然后在剩下范围内进行同样的操作(递归调用)。直到一方的首节点为NULL（递归结束）。

3 代码

  

   

    

     

    
    

     

      #include "iostream"
     
    
   

    

     

    
    

     

      #include "cstdlib"
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //问题：合并链表
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m_nValue;
     
    
   

    

     

    
    

     

      	node* m_pNext;
     
    
   

    

     

    
    

     

      }ListNode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Print_list_node(ListNode* pHead);
     
    
   

    

     

    
    

     

      ListNode* Merge_list(ListNode* pHead1, ListNode* pHead2);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void test01()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	ListNode* pHead1  = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode1 = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          ListNode* pHead2 = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode2 = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          pHead1 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode1 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pHead2 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode2 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	if (pHead1 == NULL || pNode1 == NULL || pHead2 == NULL || pNode2 == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		cout << "malloc fail" << endl;
     
    
   

    

     

    
    

     
		return ;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pHead1->m_nValue = 0;
     
    
   

    

     

    
    

     

      	pHead1->m_pNext  = pNode1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode1->m_nValue = 2;
     
    
   

    

     

    
    

     

      	pNode1->m_pNext  = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pHead2->m_nValue = 1;
     
    
   

    

     

    
    

     

      	pHead2->m_pNext  = pNode2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode2->m_nValue = 3;
     
    
   

    

     

    
    

     

      	pNode2->m_pNext  = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       	cout << "list1:\t\t";
     
    
   

    

     

    
    

     
 	Print_list_node(pHead1);		//打印链表节点信息
     
    
   

    

     

    
    

     

       	cout << "list2:\t\t";
     
    
   

    

     

    
    

     
 	Print_list_node(pHead2);		//打印链表节点信息
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       	cout << "Merge list:\t";
     
    
   

    

     

    
    

     
 	Print_list_node(Merge_list(pHead1, pHead2));		//合并后
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	test01();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：合并链表(递归算法)
     
    
   

    

     

    
    

     

      //输入：pHead1 pHead2 要合并的链表头节点指针
     
    
   

    

     

    
    

     

      //返回：合并后的头节点指针
     
    
   

    

     

    
    

     

      ListNode* Merge_list(ListNode* pHead1, ListNode* pHead2)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.考虑特殊情况
     
    
   

    

     

    
    

     
	if (pHead1 == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return pHead2;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	if (pHead2 == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return pHead1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	ListNode* pMerge = NULL;
     
    
   

    

     

    
    

     
	//2.递归思路， 
     
    
   

    

     

    
    

     
	if (pHead1->m_nValue < pHead2->m_nValue)
     
    
   

    

     

    
    

     

      	{//选取数值小的首节点为合并后的首节点
     
    
   

    

     

    
    

     

      		pMerge = pHead1;
     
    
   

    

     

    
    

     

      		pMerge->m_pNext = Merge_list(pHead1->m_pNext, pHead2);	//对余下部分进行递推
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	else
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		pMerge = pHead2;
     
    
   

    

     

    
    

     

      		pMerge->m_pNext = Merge_list(pHead1, pHead2->m_pNext);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//返回首节点指针
     
    
   

    

     

    
    

     
	return pMerge;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：打印链表所有节点
     
    
   

    

     

    
    

     

      //输入：pHead 头节点地址
     
    
   

    

     

    
    

     

      //返回：无
     
    
   

    

     

    
    

     

      void Print_list_node(ListNode* pHead)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (pHead != NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		while (pHead->m_pNext != NULL)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			cout << pHead->m_nValue << ",";	//打印节点信息
     
    
   

    

     

    
    

     

      			pHead = pHead->m_pNext;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		cout << pHead->m_nValue << endl;	//打印尾节点
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/98791683