数据结构与算法-链表
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