剑指Offer面试题:13.合并两个排序的链表

一题目:合并两个排序的链表二代码实现将链表换成数组做简单的循环和递归测试(1)循环实现(2)递归实现

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

剑指Offer面试题:13.合并两个排序的链表此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

一 题目:合并两个排序的链表

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


剑指Offer面试题:13.合并两个排序的链表

二 代码实现

template <typename T>
struct Node
{
public:
    T data;
    Node *pNext;
};

template <typename T>
class ListEx
{
private:
    Node<T> *m_pHead;
    Node<T> *m_pTail;
public:
    ListEx()
    {
        m_pTail = m_pHead = NULL;
    }
    ~ListEx()
    {
        Node<T> *pTemp = NULL;
        Node<T> *pNode = m_pHead;
        while (pNode)
        {
            pTemp = pNode;
            pNode = pNode->pNext;
            delete pTemp;
        }

        m_pHead = m_pTail = NULL;
    }
    void add(T data)
    {
        Node<T> *pNode = new Node<T>;
        pNode->data = data;
        pNode->pNext = NULL;

        if (m_pHead == NULL)
        {
            m_pTail = m_pHead = pNode;
        }

        Node<T>* pTemp = m_pTail;
        pTemp->pNext = pNode;
        m_pTail = pNode;
    }

    Node<T> *GetListHead()
    {
        return m_pHead;
    }
};
template <typename T>
Node<T>* RebuildArray(Node<T>* pNode1, Node<T>* pNode2)
{
    if (NULL == pNode1)
    {
        return pNode2;
    }
    else if (NULL == pNode2)
    {
        return pNode1;
    }
    Node<T>* pNewNode = new Node<T>;
    pNewNode = NULL;
    if (pNode1->data <= pNode2->data)
    {
        pNewNode = pNode1;
        pNewNode->pNext = RebuildArray(pNode1->pNext, pNode2);
    }
    else
    {
        pNewNode = pNode2;
        pNewNode->pNext = RebuildArray(pNode1, pNode2->pNext);
    }

    return pNewNode;
}
void main()
{
    ListEx<int> *pList1= new ListEx<int>();
    pList1->add(1);
    pList1->add(3);
    pList1->add(5);
    pList1->add(7);
    Node<int> *pHead1 = pList1->GetListHead();

    ListEx<int> *pList2= new ListEx<int>();
    pList2->add(2);
    pList2->add(4);
    pList2->add(6);
    pList2->add(8);
    Node<int> *pHead2 = pList2->GetListHead();

    Node<int>* p = RebuildArray(pHead1, pHead2);
}

将链表换成数组做简单的循环和递归测试

  (1)循环实现

void RebuildArray(int *a, int nLen1, int *b, int nLen2, int *pNew)
{
    if (NULL == a || NULL == b || 0 == nLen1 || 0 == nLen2 || NULL == pNew)
    {
        return;
    }

    int nIndex = 0;
    int i = 0;
    int j = 0;
    while (i < nLen1)
    {
        while (j < nLen2)
        {
            if (a[i] <= b[j])
            {
                pNew[nIndex++] = a[i++];
                break;
            }
            else
            {
                pNew[nIndex++] = b[j++];
            }
        }    
    }
    while(i < nLen1)
    {
        pNew[nIndex++] = a[i++];
    }
    while(j < nLen2)
    {
        pNew[nIndex++] = b[j++];
    }
}

  (2)递归实现

void RebuildArray_2(int *aStart, int *aEnd, int *bStart, int *bEnd, int *pNew)
{
    if (aStart > aEnd)
    {
        *pNew = *bStart;
        return;
    }
    else if (bStart > bEnd)
    {
        *pNew = *aStart;
        return;
    }
    if (*aStart <= *bStart)
    {
        *pNew = *aStart;
        RebuildArray_2(aStart+1, aEnd, bStart, bEnd, pNew+1);
    }
    else
    {
        *pNew = *bStart;
        RebuildArray_2(aStart, aEnd, bStart+1, bEnd, pNew+1);
    }
}
void RebuildArray_1(int *a, int nLen1, int *b, int nLen2, int *pNew)
{
    if (NULL == a || NULL == b || 0 == nLen1 || 0 == nLen2 || NULL == pNew)
    {
        return;
    }
    
    int *aStart = a;
    int *aEnd = &a[nLen1 - 1];
    int *bStart = b;
    int *bEnd = &b[nLen2 - 1];

    RebuildArray_2(aStart, aEnd, bStart, bEnd, pNew);
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120160.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • el-table自适应宽度_表格自适应大小

    el-table自适应宽度_表格自适应大小不要设置width=”110px”<el-table-columnprop=”login_id”align=”center”label=”工号”></el-table-column><el-table-columnprop=”login_id”width=”110px”align=”center”label=”工号…

  • 通达OA 工作流运行异常情况的紧急处理(图文)[通俗易懂]

    通达OA 工作流运行异常情况的紧急处理(图文)[通俗易懂]本文整理自通达OA技术交流群(QQ群号:378591362)群友交流内容。一位朋友的工作流设计和运行突然出现故障,显示的数据部分都不正常,如下图:经过重启所有服务(包括缓存服务)现象依旧。清理了cache下workflow里面的文件,没用后经查找,是前一天把cache下的workflow文件夹清掉了,缓存服务不会自动重建。重新手动建立文件夹后恢复正常。

  • 集成电路芯片半导体中英文对照术语词汇表「建议收藏」

    集成电路芯片半导体中英文对照术语词汇表「建议收藏」英语 中文 1-9   10gigabit 10Gb 1stNyquistzone 第一奈奎斯特区域 3Dfull‑waveelectromagneticsolver 3D全波电磁解算器 3-state 三态 4thgenerationsegmentedrouting 第四代分层布线技术 5Gcommercialization 5G商用 7seriesFPGA 7系列FPG

  • 医疗大数据平台的主流解决方案

    医疗大数据平台的主流解决方案多源异构数据汇聚分发系统:通过数据汇集和分发服务引擎,按照统一的数据格式和接口规范采集来自于不同厂家、不同设备类型、不同数据格式、不同传输协议的体征数据,然后进行数据存储,最后通过消息开放服务中间件实时分发至电子健康档案系统。   统一资源池的电子健康档案系统:电子健康档案系统是实施医疗信息 化管理和提供个性化医护服务的核心,它以用户或患者为中心,建立人口统计信息、既往病史、健康因素、家…

  • pig中使用的一些实例语法

    pig中使用的一些实例语法

    2021年12月15日
  • myeclipse软件下载_eclipse手机版

    myeclipse软件下载_eclipse手机版myeclipse官方下载:官方站点下载:downme(MyEclipseEnterpriseWorkbench8.0forEclipse3.5.1andWindows98/2000/NT/XP/Vista/7(11/23/2009))说明:已包含Elipse和JRE,无需安装其他即可运行的ALL-in-ONE版本)Version:8.0GA|Fil

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号