两路归并的数组与链表的实现方法

代码如下:

#include<iostream>
#include<assert.h>
using namespace std;
struct node
{
    int val;
    node * next;
    node(int v)
    {
        val=v;
        next=NULL;
    }
};

node * merge(node* list1 , node * list2)
{
    assert(list1!=NULL&&list2!=NULL);
    node * res;
    if(list1->val<=list2->val)
    {
        res=list1;
        list1=list1->next;
    }
    else
    {
        res=list2;
        list2=list2->next;
    }
    node * p = res;
    node *p1 =list1,*p2 =list2;

while(p1!=NULL&&p2!=NULL)
    {
        if(p1->val<=p2->val)
        {
            p->next=p1;
            p=p->next;
            p1=p1->next;
        }
        else
        {
            p->next=p2;
            p=p->next;
            p2=p2->next;
        }
    }

while(p1!=NULL)
    {
        p->next=p1;
        p=p->next;
        p1=p1->next;
    }
    while(p2!=NULL)
    {
        p->next=p2;
        p=p->next;
        p2=p2->next;
    }
    return res;
}

int * merge(int * arr1,int la, int * arr2,int lb)
{
    int i=0,j=0;
    int * arr = new int[la+lb];
    int t=0;
    while(i<la&&j<lb)
    {
        if(arr1[i]<=arr2[j])
        {
            arr[t++]=arr1[i];
            i++;
        }
        else
        {
            arr[t++]=arr2[j];
            j++;
        }
    }
    while(i<la)
    {
        arr[t++]=arr1[i];
        i++;
    }
    while(j<lb)
    {
        arr[t++]=arr2[j];
        j++;
    }
    return arr;
}

void setLinkData(node * & list1 , node * & list2)
{
    node * node1 = new node(2);
    node * node2 = new node(3);
    node * node3 = new node(7);
    node * node4= new node(9);
    node1->next=node2;
    node2->next=node3;
    node3->next=node4;
    list1=node1;

node * node5 = new node(1);
    node * node6 = new node(4);
    node * node7 = new node(6);
    node * node8 = new node(8);
    node5->next=node6;
    node6->next=node7;
    node7->next=node8;
    list2=node5;
}

int main()
{
    node * list1;
    node * list2;
    setLinkData(list1,list2);
    int arr1[]={1,6,15,17,19};
    int arr2[]={2,4,6,8,10};
    int * arr = merge(arr1,5,arr2,5);
    node * ans = merge(list1,list2);
    //Print result
    int length=10;
    for(int i=0;i<10;i++)
    {
        cout<<*arr<<endl;
        arr++;
    }
    while(ans!=NULL)
    {
        cout<<ans->val<<endl;
        ans=ans->next;
    }
    return 0;
}

(0)

相关推荐

  • 两路归并的数组与链表的实现方法

    复制代码 代码如下: #include<iostream>#include<assert.h>using namespace std;struct node{    int val;    node * next;    node(int v)    {        val=v;        next=NULL;    }}; node * merge(node* list1 , node * list2){    assert(list1!=NULL&&lis

  • C++归并法+快速排序实现链表排序的方法

    本文主要介绍了C++归并法+快速排序实现链表排序的方法,分享给大家,具体如下: 我们可以试用归并排序解决: 对链表归并排序的过程如下. 找到链表的中点,以中点为分界,将链表拆分成两个子链表.寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点. 对两个子链表分别排序. 将两个排序后的子链表合并,得到完整的排序后的链表 上述过程可以通过递归实现.递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链

  • js数组的五种迭代方法及两种归并方法(推荐)

    js数组的五种迭代方法及两种归并方法(推荐) <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta ht

  • 使用python实现数组、链表、队列、栈的方法

    引言 什么是数据结构? 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成. 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中. 比如:列表,集合和字典等都是数据结构 N.Wirth:"程序=数据结构+算法" 数据结构按照其逻辑结构可分为线性结构.树结构.图结构 线性结构:数据结构中的元素存在一对一的互相关系. 树结构:数据结构中的元素存在一对多的互相关系. 图结构:数据结构中的元素存在多对多的互相关系. 数组 在python中是没有数

  • Redis数组和链表深入详解

    1.数组和链表基础知识 数组: 数组会在内存中开辟一块连续的空间存储数据,这种存储方式有利也有弊端.当获取数据的时候,直接通过下标值就可以获取到对应的元素,时间复杂度为O(1).但是如果新增或者删除数据会移动大量的数据,时间复杂度为O(n).数组的扩容机制是:如果数组空间不足,会先开辟一块新的空间地址,将原来的数组复制到新的数组中. 链表: 链表不需要开辟连续的内存空间,其通过指针将所有的数据连接起来.新增或者删除的时候只需要将指针指向的地址修改就行了,时间复杂度为O(1).但是查询的时间复杂度

  • Java面向对象基础知识之数组和链表

    数组的优点: 随机访问性强 查找速度快 数组要求是一块连续的内存空间来存储,这就要求在物理上这一片空间是连续的,每个元素都有指定的索引index指向内存地址,因此查询对时候,可根据index快速找到对应地址存储的信息,此为查询快. 数组的缺点: 插入和删除效率低 数组进行增删的时候,就必须将目标位置后的所有元素都整体移动,因此就比较耗时,此为增删慢. 可能浪费内存 内存空间要求高,必须有足够的连续内存空间. 数组大小固定,不能动态拓展 链表的优点: 插入删除速度快 链表在物理上是动态地分配储存空

  • C++如何用数组模拟链表

    目录 前言 1.单链表 2.双链表 总结 前言 链表是指由一系列储存在非连续储存空间 结点组成的储存结构.每个结点由两部分组成:一是储存元素的数据域,一是储存下一个节点地址的指针域.用数组模拟链表可以十分清晰明了地理解这一定义. 在这里,我们简单地介绍一下单链表和双链表两种链表以及用数组模拟实现它们的方式. 1.单链表 单链表是指针方向单向的链表,即a结点的指针域储存着b结点的地址,而b结点的指针域内没有储存a结点的地址.在访问时,可以由a到b访问,而不能由b到a访问. 如图可以清晰地看到,各个

  • C语言修炼之路悟彻数组真妙理 巧用下标破万敌下篇

    目录 (壹)冒泡排序 1.1冒泡排序的设计 1.2冒泡排序的步骤 1.3冒泡排序的实现 (贰)数组作为函数参数 2.1冒泡排序函数的错误设计 2.2冒泡排序函数的正确设计 (叁)对数组名的拓展解析 (壹)冒泡排序 1.1冒泡排序的设计 冒泡排序(Bubble Sort)也是一种简单直观的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢

  • C++中的数组、链表与哈希表

    目录 数组和链表 数组 链表 什么是链表? 链表的操作 双向链表(list) list的成员函数 哈希表 什么是哈希表? 哈希碰撞 哈希表应用场景 构建哈希表 哈希表基本使用 Leetcode对应题目 前缀和 差分数组 滑动窗口 二分查找 数组和链表 C++的数组和链表分别是什么?分别有什么种类?它们都有什么特性?针对这些特征,使用情形是什么? 数组 什么是数组? 一个数组就像是一个变量,它可以存储一组值,但是所有值都是相同的数据类型. 一个int数组定义:int hours [6] 该数组类型

  • java 两个数组合并的几种方法

    本文介绍了java 两个数组合并的几种方法,分享给大家,也给自己留个笔记 需求:两个字符串合并(如果想去重复,参考下一篇--数组去重复及记录重复个数) //方法一 Arrays类 String[] a = {"A","B","C"}; String[] b = {"D","E"}; // List<String> list = Arrays.asList(a); --OK // List<

随机推荐