剑指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)


相关推荐

  • JavaScript 基本知识

    JavaScript 基本知识bilibiliJS视频链接:https://www.bilibili.com/video/BV1W54y1J7Ed?p=2&spm_id_from=pageDrivervscode配置html:https://blog.csdn.net/caohongxing/article/details/108632859目录JS来源JavaScript核心由三部分组成书写位置:行内式,内嵌式,外链式变量:var准备一个容器,变量名有规格且区分大小写JS中的数据:基本数据类型和引用数据类型.

    2022年10月20日
  • python数据库操作之sqlalchemy逆向工程

    python数据库操作之sqlalchemy逆向工程依赖安装pipinstallsqlacodegen数据库配置config.pyimportosHOST=’localhost’PORT=3306USERNAME=’root’PASSWORD=’root’DB=’demo’DB_URI=f’mysql+pymysql://{USERNAME}:{PASSWORD}@{HOST}:{PORT}/{DB}’#自动生成modelsos.system(f’sqlacodegen{DB_URI}

  • idea2018激活码【2021免费激活】[通俗易懂]

    (idea2018激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html1M3Q9SD5XW-eyJsa…

  • 怎么禁止使用360浏览器(怎么才能把自带的浏览器停用)

    360浏览器6.2自带了FlashPlayer,版本为11.6,而我需要使用最新版的FlashPlayer11.9,我安装了最新版的FlashPlayer11.9后,浏览网页时,360浏览器6.2默认使用的是自带的FlashPlayer11.6因此我们必须禁用掉360浏览器自带的FlashPlayer11.6——————————

  • webStorm快捷键整理「建议收藏」

    webStorm快捷键整理「建议收藏」一些自己会用的webstorm快捷键,持续更新

  • 笔记本电脑无线投屏电视怎么设置(电脑投屏电视怎么设置)

    家用笔记本电脑和电视无线投屏设置1.打开电视,点我的应用,找到无线投屏按钮,遥控器点击。2.点Miracast3.笔记本电脑点右下角“通知”按钮,点击“连接”4.点击搜索到的电视名称,进行连接。5.电视节目会出现如下图所示提示,表示连接成功。6.点击“投影”可以更改笔记本和电视的显示方式。over!…

发表回复

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

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