链表专项练习题三 | 合并两个有序链表


问题描述

输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
合并链表示意图
如图所示,链表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;
}

参考链接

合并两个有序链表
合并两个有序单链表

本文发表于2018年11月14日 21:03
阅读 3768 讨论 0 喜欢 1

抢先体验

扫码体验
趣味小程序
文字表情生成器

闪念胶囊

你要过得好哇,这样我才能恨你啊,你要是过得不好,我都不知道该恨你还是拥抱你啊。

直抵黄龙府,与诸君痛饮尔。

那时陪伴我的人啊,你们如今在何方。

不出意外的话,我们再也不会见了,祝你前程似锦。

这世界真好,吃野东西也要留出这条命来看看

快捷链接
网站地图
提交友链
Copyright © 2016 - 2021 Cion.
All Rights Reserved.
京ICP备2021004668号-1