在我自己的开发生涯中，其实用到链表的情况很少，但是不可否认的是，链表对于 插入、删除元素 比较频繁的场景，是有较大性能上的提升，所以我认为，对于链表这种数据结构，作为前端工程师的我们也应该熟练掌握，本篇文章就准备聊聊关于它的一道较为经典的算法题，废话不多说，开搞！
什么是链表
在开始讲解算法题之前，我们先看看链表的定义与特征
链表是一种 线性结构，它的每一个元素除了存放本身的值以外，还存放了 指向其他元素的指针，通过指针来将所有元素串联起来，与数组的区别有如下几点：
- 链表的元素存储空间 不一定连续，而数组中的元素存储空间 一定是连续的
- 链表的 查询效率较低，因为必须从头开始查找，而数组可以直接根据索引进行查找
- 链表的 插入与删除 操作效率高，因为只需要调整指针指向即可，而数组是会将原本的元素 依次进行移动
合并两个有序链表
在知道了链表的定义之后，我们来做下这道经典的 合并两个有序链表，题目如下：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
我们从题目中可以提取中两个关键点
对于该题目，一共有两种解决方式
- 双指针：为了充分利用已经有序的特性，我们应该很自然的想到双指针的方式进行合并，通过双指针分别指向两个列表，我们可以通过一次遍历，依次将两个列表中相对较小的节点放在前面，以达到升序的目的
- 递归：通过不断把需要合并的链表规模缩小，最终实现链表的整合
下面依次给出具体代码
双指针：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
if(list1 === null) return list2
if(list2 === null) return list1
const head = new ListNode(0)
let cur = head
while(list1 && list2) {
if(list1.val <= list2.val) {
cur.next = list1
list1 = list1.next
}else {
cur.next = list2
list2 = list2.next
}
cur = cur.next
}
if(!list1) {
cur.next = list2
}
if(!list2) {
cur.next = list1
}
return head.next
}
|
递归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
if(list1 === null) return list2
if(list2 === null) return list1
if(list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next,list2)
return list1
}else {
list2.next = mergeTwoLists(list1,list2.next)
return list2
}
}
|
