摘要:关于链表区别于数组,数组的所有的元素在内存中都是连续存储的,而链表则是分散在内存中的,通过指针连接起来的一种数据结构。接下来,我们尝试使用合并两个有序链表。
关于链表
一些准备区别于数组,数组的所有的元素在内存中都是连续存储的,而链表则是分散在内存中的,通过指针连接起来的一种数据结构。接下来,我们尝试使用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);
结果如下:
以上代码中,都省去了参数合法性校验的过程,真实环境里是需要的。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/89206.html
摘要:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。无非是依次将两个链表每个节点的值对比,取出值较小的节点,添加到新链表末尾。将剩余链表传回递归函数。 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 Merge two sorted linked lists and return it as a n...
摘要:分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法跟动态规划的明显区别。 Time:2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿 题目:Merge K...
摘要:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例输入输出答案参考 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4输出:1->1->2->3->4->4 答案参考: /** * Definition for singly-linked list...
摘要:什么意思呢比如上方合并链表的代码,分别明确函数的参数和返回值是什么参数是两个合并的链表结点头结点。返回值是合并后的链表。 Time:2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿 题目:Merge Two Sorted Lists Merge two sorted linked lists and re...
摘要:示例输入输出示例输入输出示例输入输出提示两个链表的节点数目范围是和均按非递减顺序排列递归法分析递归法,和之前的一样,还是需要先设置跳出判断,这里设置为空的时候跳出。 ...
阅读 1215·2023-04-26 00:47
阅读 3568·2021-11-16 11:53
阅读 795·2021-10-08 10:05
阅读 2739·2021-09-22 15:19
阅读 2981·2019-08-30 15:55
阅读 2755·2019-08-29 16:55
阅读 2921·2019-08-29 15:20
阅读 1111·2019-08-23 16:13