black927

black927 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

black927 提出了问题 · 10月17日

这种树形操作求大佬推荐插件或代码

image.png

关注 3 回答 1

black927 赞了文章 · 3月19日

js合并有序链表

关于链表

区别于数组,数组的所有的元素在内存中都是连续存储的,而链表则是分散在内存中的,通过指针连接起来的一种数据结构。接下来,我们尝试使用js合并两个有序链表。

一些准备

首先我们需要声明一些我们需要用到的函数。

链表中的节点

每一个节点通常最少有两个属性,一个表示该节点的值,可以用key来表示,另外一个就是指向下一个节点的指针,可以用next表示。
先声明一个Node类:

function Node (key) {
    this.key = key;
    this.next = null;
}

链表类

接着,声明一个链表类LinkedList:

function LinkedList () {
    //表示链表的长度
    this.length = 0;
    //表示链表的头结点(第一个节点)
    this.head = null;
}

链表的插入节点方法

然后,再声明一个基本的链表方法append,用来向链表尾部插入一个新节点:

LinkedList.prototype.append = function (key){
    var node = new Node(key);
    //如果链表还没有节点
    if (!this.head) {
        this.head = node;
    } else {
        //通过循环找到最后一个节点,然后让最后一个节点指向新节点
        var current = this.head;
        while(current.next){
            current = current.next;
        }
        current.next = node;
    }
    // 修改链表的长度
    this.length++;
}

构造两个有序链表

我们的目的是合并有序链表,所以这里,我们先用两个有序数组,去构建两个有序链表:

var arr1 = [2, 4, 6, 8];
var arr2 = [1, 3, 5, 7];
var list1 = new LinkedList();
var list2 = new LinkedList();

arr1.forEach(function(key){
    list1.append(key);
});
arr2.forEach(function(key){
    list2.append(key);
});

合并有序链表

最简单的方案

就是把两个链表中所有key都拿出来放进一个数组里,庵后,再对数组排序,根据数组,重新构建一个链表。

function mergeLinkedList (list1, list2) {
    // 存放两个链表key的数组
    var array = [];
    // 最终需要返回的新链表
    var list = new LinkedList();
    // 第一个链表的头节点
    var listHead1 = list1.head;
    // 第二个链表的头节点
    var listHead2 = list2.head;

    // 把第一个链表的所有key存进数组
    while (listHead1) {
        array.push(listHead1.key);
        listHead1 = listHead1.next;
    }
    // 把第二个链表的所有key存进数组
    while (listHead2) {
        array.push(listHead2.key);
        listHead2 = listHead2.next;
    }
    // 对数组排序
    array = array.sort(function(a, b){
        return a - b;
    })
    // 使用数组重新构建一个链表
    array.forEach(function(key){
        list.append(key);
    });

    return list;
}

按顺序把两个链表的key插入到新链表

function mergeLinkedList (list1, list2) {
    var list = new LinkedList();
    // 第一个链表的头节点
    var current1 = list1.head;
    // 第二个链表的头节点
    var current2 = list2.head;

    // 用循环把两个链表的key按顺序插入到新链表
    while (current1 && current2) {
        if (current1.key < current2.key) {
            list.append(current1.key);
            current1 = current1.next;
        } else {
            list.append(current2.key);
            current2 = current2.next;
        }
    }

    // 找到新链表的最后一个节点
    var current = list.head;
    while(current.next){
        current = current.next;
    }

    // 循环完成以后,把第二个链表剩余部分插入到新链表
    if (current2) {
        while (current2) {
            list.append(current2.key);
            current2 = current2.next;
        }
    }
    // 循环完成以后,把第一个链表剩余部分插入到新链表
    if (current1) {
        while (current1) {
            list.append(current1.key);
            current1 = current1.next;
        }
    }

    return list;
}

合并到第一个链表

function mergeLinkedList (list1, list2) {
    var listHead1 = list1.head;
    var listHead2 = list2.head;
    var previous = listHead1;

    // 如果第二个链表的首节点key小于第一个链表的首节点key
    // 则构造一个新节点,并把新节点插入到第一个链表头部
    if (listHead1.key > listHead2.key) {
        var node = new Node(listHead2.key);
        node.next = listHead1;
        list1.head = listHead1 = previous = node;
        listHead2 = listHead2.next;
    }
    // 循环比较两个链表的key,把第二个链表中的key插入到第一个链表合适的位置
    while (listHead1 && listHead2) {
        if (listHead2.key < listHead1.key) {
            var node = new Node(listHead2.key);
            node.next = previous.next;
            previous.next = node;
            previous = node;
            listHead2 = listHead2.next;
        } else {
            previous = listHead1;
            listHead1 = listHead1.next; 
        }
    }
    // 如果第二个链表比较长,则把剩余部分插入到第一个链表
    while (listHead2) {
        var node = new Node(listHead2.key);
        if (listHead1) {
            listHead1.next = node;
            listHead1 = node;                    
        } else if (previous) {
            previous.next = node;
            previous = node;    
        }

        listHead2 = listHead2.next;
    }

    // 修正第一个链表的长度
    list1.length = list1.length + list2.length;
    return list1;
}

结果验证

还是构造两个有序链表

var arr1 = [2, 4, 6, 8];
var arr2 = [1, 3, 5, 7];
var list1 = new LinkedList();
var list2 = new LinkedList();
arr1.forEach(function(key){
    list1.append(key);
});
arr2.forEach(function(key){
    list2.append(key);
});
var list = mergeLinkedList(list1, list2);

自控制台查看结果:
图片描述

换一组测试数据(arr1和arr2调换一下):

var arr2 = [2, 4, 6, 8];
var arr1 = [1, 3, 5, 7];
var list1 = new LinkedList();
var list2 = new LinkedList();
arr1.forEach(function(key){
    list1.append(key);
});
arr2.forEach(function(key){
    list2.append(key);
});
var list = mergeLinkedList(list1, list2);

看结果:
图片描述

来一个复杂点的测试数据:

var arr1 = [99, 100, 104, 106];
var arr2 = [1, 3, 5, 7, 102, 103, 107];
var list1 = new LinkedList();
var list2 = new LinkedList();
arr1.forEach(function(key){
    list1.append(key);
});
arr2.forEach(function(key){
    list2.append(key);
});
var list = mergeLinkedList(list1, list2);

结果如下:
图片描述

以上代码中,都省去了参数合法性校验的过程,真实环境里是需要的。

查看原文

赞 16 收藏 10 评论 0

black927 关注了用户 · 3月18日

吉祥物 @jixiangwu

关注 50

black927 关注了专栏 · 3月18日

我们一起进大厂

微信搜索:三太子敖丙

关注 5867

black927 关注了专栏 · 3月18日

cxuan的技术园地

Java后端开发,欢迎关注个人微信公众号 Java建设者 及时关注最新技术文章。

关注 7808

black927 关注了专栏 · 3月18日

SegmentFault 之声

在这里,我们将为你推送 SegmentFault 思否公司官方合作信息,和合作伙伴最新动态。SegmentFault 思否是中国领先的开发者社区和技术媒体,中国最大的 Hackathon 组织者。我们致力于成为科技企业和开发者沟通的桥梁,帮助科技企业和开发者对话。

关注 10132

black927 关注了专栏 · 3月18日

SegmentFault 行业快讯

第一时间为开发者提供行业相关的实时热点资讯

关注 25244

black927 关注了专栏 · 3月18日

前端笔记本

此后如没有炬火,我便是唯一的光🔥

关注 5937

black927 关注了专栏 · 3月18日

CodeSheep的技术分享

分享虚拟化、容器化、API化、微服务化的WEB技术,更多务实、能看懂、可复现的原创文章尽在作者公众号 CodeSheep,欢迎订阅

关注 5174

black927 关注了用户 · 3月18日

日拱一兵 @tanrigongyibing

欢迎关注,公众号「日拱一兵」,以读侦探小说思维趣味轻松学习Java技术

送你《1000G 免费精选技术学习资料》(2020 年最新)
https://mp.weixin.qq.com/s/9p...

关注 19391

认证与成就

  • 获得 0 次点赞
  • 获得 0 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 0 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 3月18日
个人主页被 48 人浏览