问题描述
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
如图所示,链表1与链表2合并,最终得到链表3。
问题分析
因为两个链表上的结点都是递增排序的,合并后的链表也是递增排列的,那么合并后的链表头结点一定是两个链表头结点中较小的那一个。
我们可以先取出最小结点,然后再次对比两个链表的头结点,再次取出最小结点,依次处理,直至其中一个链表取空,然后将另一个链表所剩的结点全部拼接在合并链表的最后,即可完成对两个链表的递增合并。
如图所示
代码实现
递归法:
ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
if(pHead1==NULL) return pHead2;
if(pHead2==NULL) return pHead1;
ListNode* pMergeHead = NULL;
if( pHead1->m_nValue < pHead2->m_nValue )
{
pMergeHead = pHead1;
pMergeHead->m_pNext = Merge( pHead1->m_pNext , pHead2->m_pNext );
}else{
pMergeHead = pHead2;
pMergeHead->m_pNext = Merge( pHead1->m_pNext , pHead2->m_pNext );
}
return pMergeHead;
}
迭代法:
ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
if(pHead1==NULL) return pHead2;
if(pHead2==NULL) return pHead1;
ListNode* pMergeHead = NULL;
// 获取头结点
if( pHead1->m_nValue < pHead2->m_nValue )
{
pMergeHead = pHead1;
pHead1 = pHead1->m_pNext;
}else{
pMergeHead = pHead2;
pHead2 = pHead2->m_pNext;
}
// 处理中间结点
while( pHead1 != NULL && pHead2 != NULL ){
if( pHead1->m_nValue < pHead2->m_nValue )
{
pMergeHead->m_pNext = pHead1;
pHead1 = pHead1->m_pNext;
}else{
pMergeHead->m_pNext = pHead2;
pHead2 = pHead2->m_pNext;
}
}
// 处理剩余结点
if( pHead1 != NULL ){
pMergeHead->m_pNext = pHead1;
}elseif( pHead2 != NULL ){
pMergeHead->m_pNext = pHead2;
}
return pMergeHead;
}
参考链接
合并两个有序链表
合并两个有序单链表