数据结构与算法-生成链表本地环境及合并两个有序链表
2021/9/24 1:41:05
本文主要是介绍数据结构与算法-生成链表本地环境及合并两个有序链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数据结构与算法-链表
1.建立链表
在做链表相关的leetcode算法题中,会发现没有本地环境,如何搭建链表的本地环境(JavaScript)。
有两种方式:1.对象;2.构造函数加原型来创建对象
首先建立链表,其包括每个节点及每个节点的val和next。
//创建两个链表:1->2->4, 1->3->4 //方法1:对象 var l1 = { val: 1, next: { val: 2, next: { val: 4, next: null }, }, }; var l2 = { val: 1, next: { val: 3, next: { val: 4, next: null }, }, }; //方法2:构造函数加原型来创建对象(更为自由,每个链表有一个头指针head) function LinkedList() { //属性 this.head = null //记录链表长度 this.length = 0 //内部类:节点类 function ListNode(val) { this.val = val this.next = null } //1.追加方法 LinkedList.prototype.append = function (val) { var newNode = new ListNode(val) if (this.length == 0) { this.head = newNode } else { var current = this.head while (current.next) { current = current.next } current.next = newNode } //3.length+1 this.length += 1 } } var l1 = new LinkedList() l1.append(1) l1.append(2) l1.append(4) var l2 = new LinkedList() l2.append(1) l2.append(3) l2.append(4)
2.算法题-合并上述两个有序链表
对于链表这种有连接关系的数据结构,我们可以采用递归和迭代的方式来解答。
2.1方法1:递归
//方法1:对象 var l1 = { val: 1, next: { val: 2, next: { val: 4, next: null }, }, }; var l2 = { val: 1, next: { val: 3, next: { val: 4, next: null }, }, }; //递归(采用第一种方式建立两个链表) ar mergeTwoLists = (l1, l2) => { if (!l1) { return l2; } else if (!l2) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l2.next, l1); return l2; } }; var l3 = mergeTwoLists(l1, l2) //1.定义变量 var current = l3 var listString = '' //2.循环获取一个个节点 while (current) { listString += current.val + ' ' current = current.next } console.log(listString)//结果1 1 2 3 4 4
2.2方法2:迭代
//方法2:构造函数加原型来创建对象(更为自由,每个链表有一个头指针head) function LinkedList() { //属性 this.head = null //记录链表长度 this.length = 0 //内部类:节点类 function ListNode(val) { this.val = val this.next = null } //1.追加方法 LinkedList.prototype.append = function (val) { var newNode = new ListNode(val) if (this.length == 0) { this.head = newNode } else { var current = this.head while (current.next) { current = current.next } current.next = newNode } //3.length+1 this.length += 1 } } var l1 = new LinkedList() l1.append(1) l1.append(2) l1.append(4) var l2 = new LinkedList() l2.append(1) l2.append(3) l2.append(4) //迭代方法 const mergeTwoLists = (l1, l2) => { const newList = { val: -1, next: null, }; let tempList = newList; while (l1 && l2) { if (l1.val <= l2.val) { tempList.next = l1; l1 = l1.next; } else if (l1.val > l2.val) { tempList.next = l2; l2 = l2.next; } tempList.next.next = null; tempList = tempList.next; } tempList.next = l1 || l2; return newList.next; }; var l3 = mergeTwoLists(l1.head, l2.head) //1.定义变量 var current = l3 var listString = '' //2.循环获取一个个节点 while (current) { listString += current.val + ' ' current = current.next } console.log(listString)结果1 1 2 3 4 4
3.参考
leetcode相关解法
这篇关于数据结构与算法-生成链表本地环境及合并两个有序链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30PS网页切图项目实战:初学者必备指南
- 2024-09-30Span标签项目实战:新手入门教程
- 2024-09-309D资料入门指南:轻松掌握基础操作
- 2024-09-30如何获取和利用变形资料:新手入门指南
- 2024-09-30弹性盒子布局资料:新手必读教程
- 2024-09-30手把手教你如何使用“点击加载资料”功能
- 2024-09-30封装资料入门教程:轻松掌握封装资料的方法与技巧
- 2024-09-30钢琴效果资料:新手入门指南
- 2024-09-30滚动吸顶资料详解:轻松掌握网页常见布局技巧
- 2024-09-30后台交互资料详解:新手入门教程