在做链表相关的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)
对于链表这种有连接关系的数据结构,我们可以采用递归和迭代的方式来解答。
//方法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:构造函数加原型来创建对象(更为自由,每个链表有一个头指针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
leetcode相关解法