线性表数据结构——链表

一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。在js中链表长这样

const list = {head: {value: 6next: {value: 10                                             next: {value: 12next: {value: 3next: null    }}}}}
};

一、概念

链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用讲做链

其中，data中保存着数据，next保存着下一个链表的引用。上图中，我们说 data2 跟在 data1 后面，而不是说 data2 是链表中的第二个元素。上图，值得注意的是，我们将链表的尾元素指向了 null 节点，表示链接结束的位置。

由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为 头节点，表示链表的头部。进过改造，链表就成了如下的样子

1、插入节点图解

向链表中插入一个节点的效率很高，需要修改它前面的节点(前驱)，使其指向新加入的节点，而将新节点指向原来前驱节点指向的节点即可。下面我将用图片演示如何在 data2 节点 后面插入 data4 节点。

2、删除节点图解

同样，从链表中删除一个节点，也很简单。只需将待删节点的前驱节点指向待删节点的，同时将待删节点指向null，那么节点就删除成功了。下面我们用图片演示如何从链表中删除 data4 节点

二、链表的基本操作

数据结构的操作一般涉及到增、删、改、查 4 种情况，链表的操作也基本上是这 4 种情况。我们一起来看一下链表的基本操作

1. 链表的结构定义

1.1. 基本定义

链表是由链节点通过 next链接而构成的，我们可以先定义一个简单的「链节点类」，再来定义完整的「链表类」

链节点类（即 ListNode 类）

使用成员变量 val表示数据元素的值，使用指针变量 next表示后继指针。

链表类（即 LinkedList 类)

使用一个链节点变量 head 来表示链表的头节点。

// 链表节点类
class ListNode {constructor(val, next = null) {this.val = val; // 节点的值this.next = next; // 指向下一个节点的引用}
}// 链表类
class LinkedList {constructor() {this.head = null; // 链表的头节点，初始时为空}
}

1.2. 建立一个线性链表

满足以下条件

1. 从所给线性表的第 1 个数据元素开始依次获取表中的数据元素。
2. 每获取一个数据元素，就为该数据元素生成一个新节点，将新节点插入到链表的尾部。
3. 插入完毕之后返回第 1个链节点的地址。

// 链表节点类
class ListNode {constructor(value) {this.value = value; // 节点的值this.next = null;  // 下一个节点的引用}
}// 链表类
class LinkedList {constructor() {this.head = null; // 链表的头节点}// 根据数据创建链表create(data) {this.head = new ListNode(0); // 创建一个带有虚拟头节点的链表let cur = this.head; // 初始化当前节点为头节点for (let i = 0; i < data.length; i++) {const node = new ListNode(data[i]); // 创建新的节点cur.next = node; // 将当前节点的 next 指向新节点cur = cur.next; // 更新当前节点为新节点，继续下一个循环}}
}// 创建链表并根据数据初始化
const linkedList = new LinkedList();
const data = [1, 2, 3];
linkedList.create(data); // 使用 create 方法初始化链表

1.3. 小测试：求线性链表的长度

使用指针变量 cur 顺着链表 next指针进行移动，并使用计数器 count记录元素个数。

1. 让指针变量 cur指向链表的第 1 个链节点。
2. 顺着链节点的 next指针遍历链表，指针变量 cur 每指向一个链节点，计数器就做一次计数。
3. 等 cur指向为空时结束遍历，此时计数器的数值就是链表的长度，将其返回即可

// 链表节点类
class ListNode {constructor(value) {this.value = value; // 节点的值this.next = null;  // 下一个节点的引用}
}// 链表类
class LinkedList {constructor() {this.head = null; // 链表的头节点}// 根据数据创建链表create(data) {this.head = new ListNode(0); // 创建一个带有虚拟头节点的链表let cur = this.head; // 初始化当前节点为头节点for (let i = 0; i < data.length; i++) {const node = new ListNode(data[i]); // 创建新的节点cur.next = node; // 将当前节点的 next 指向新节点cur = cur.next; // 更新当前节点为新节点，继续下一个循环}}// 获取链表的长度length() {let count = 0;let cur = this.head; // 从头节点开始遍历while (cur) {count++; // 增加计数器cur = cur.next; // 移动到下一个节点}return count; // 返回链表的长度}
}// 创建链表并根据数据初始化
const linkedList = new LinkedList();
const data = [1, 2, 3];
linkedList.create(data);// 获取链表的长度
const listLength = linkedList.length();
console.log(`链表的长度为: ${listLength}`);

2. 查找元素

在链表中查找值为 val的元素：从头节点 head开始，沿着链表节点逐一进行查找。如果查找成功，返回被查找节点的地址；否则返回 None。

1. 让指针变量 cur指向链表的第 1个链节点。
2. 顺着链节点的 next指针遍历链表，如果遇到 cur.val==val，则返回当前指针变量 cur。
3. 如果 cur指向为空时也未找到，则该链表中没有值为 val的元素，则返回 None

// 链表节点类
class ListNode {constructor(value) {this.value = value; // 节点的值this.next = null;  // 下一个节点的引用}
}// 链表类
class LinkedList {constructor(data = []) {this.head = null; // 链表的头节点if (data.length > 0) {this.create(data); // 如果传入了数组，则自动初始化链表}}// 创建链表create(data) {this.head = new ListNode(0); // 创建一个带有虚拟头节点的链表let cur = this.head; // 初始化当前节点为头节点for (let i = 0; i < data.length; i++) {const node = new ListNode(data[i]); // 创建新的节点cur.next = node; // 将当前节点的 next 指向新节点cur = cur.next; // 更新当前节点为新节点，继续下一个循环}}// 获取链表的长度length() {let count = 0;let cur = this.head; // 从头节点开始遍历while (cur) {count++; // 增加计数器cur = cur.next; // 移动到下一个节点}return count; // 返回链表的长度}// 查找链表中具有特定值的元素find(val) {let cur = this.head; // 从头节点开始遍历while (cur) {if (val === cur.value) {return cur; // 如果找到值等于 val 的元素，返回该元素}cur = cur.next; // 否则继续遍历下一个节点}return null; // 如果没有找到匹配元素，返回 null}
}// 创建链表并自动初始化
const data = [1, 2, 3];
const linkedList = new LinkedList(data);// 获取链表的长度
const listLength = linkedList.length();
console.log(`链表的长度为: ${listLength}`);

3. 插入元素

链表中插入元素操作分为三种：

链表头部插入元素：在链表第 1 个链节点之前插入值为 val的链节点。

链表尾部插入元素：在链表最后 1 个链节点之后插入值为 val的链节点。

链表中间插入元素：在链表第 i 个链节点之前插入值为 val的链节点。

3.1. 链表头部插入元素

链表头部插入元素：在链表第 1 个链节点之前插入值为 val的链节点

1. 先创建一个值为 val的链节点 node
2. 然后将 node 的 next指针指向链表的头节点 head。
3. 再将链表的头节点 head指向 node。

  // 在链表头部插入元素insertFront(val) {const node = new ListNode(val); // 创建新节点node.next = this.head; // 将新节点的 next 指向原头节点this.head = node; // 更新头节点为新节点}

3.2. 链表尾部插入元素

链表尾部插入元素：在链表最后 1 个链节点之后插入值为 val的链节点。

1. 先创建一个值为 val的链节点 node。
2. 使用指针 cur指向链表的头节点 head。
3. 通过链节点的 next 指针移动 cur指针，从而遍历链表，直到 cur.next为 None。
4. 令 cur.next指向将新的链节点 node。

 // 在链表尾部插入元素insertRear(val) {const node = new ListNode(val); // 创建新节点let cur = this.head; // 从头节点开始遍历while (cur.next) {cur = cur.next; // 移动到下一个节点，直到找到最后一个节点}cur.next = node; // 将最后一个节点的 next 指向新节点，实现插入}

3.3. 链表中间插入元素

链表中间插入元素：在链表第 i个链节点之前插入值为 val的链节点。

使用指针变量 cur和一个计数器 count。令 cur 指向链表的头节点，count 初始值赋值为 0。

沿着链节点的 next 指针遍历链表，指针变量 cur 每指向一个链节点，计数器就做一次计数。

当遍历到第 index−1个链节点时停止遍历。

创建一个值为 val的链节点 noden。

将 node.next 指向 cur.next。

然后令 cur.next指向 node

 // 在链表中指定位置插入元素insertInside(index, val) {let count = 0;let cur = this.head;while (cur && count < index - 1) {count++;cur = cur.next;}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}const node = new ListNode(val); // 创建新节点node.next = cur.next; // 将新节点的 next 指向当前节点的下一个节点cur.next = node; // 更新当前节点的 next，实现插入}

4. 改变元素

将链表中第 i个元素值改为 val：首先要先遍历到第 i个链节点，然后直接更改第 i个链节点的元素值。具体做法如下：

1. 使用指针变量 cur和一个计数器 count。令 cur指向链表的头节点，count初始值赋值为 0。
2. 沿着链节点的 next指针遍历链表，指针变量 cur每指向一个链节点，计数器就做一次计数。
3. 当遍历到第 index个链节点时停止遍历。
4. 直接更改 cur 的值 val。

 // 更改链表中第 i 个元素的值为 valchange(index, val) {let count = 0;let cur = this.head; // 从头节点开始遍历while (cur && count < index) {count++; // 增加计数器cur = cur.next; // 移动到下一个节点}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}cur.value = val; // 更改指定位置的元素的值为 val}

5. 删除元素

链表的删除元素操作与链表的查找元素操作一样，同样分为三种情况：

• 链表头部删除元素：删除链表的第 1 个链节点。
• 链表尾部删除元素：删除链表末尾最后 1 个链节点。
• 链表中间删除元素：删除链表第 i个链节点

5.1. 链表头部删除元素

直接将 self.head 沿着 next 指针向右移动一步即可

  // 从链表头部删除元素removeFront() {if (this.head) {this.head = this.head.next; // 将头节点更新为下一个节点，实现删除头部元素}}

5.2. 链表尾部删除元素

1. 先使用指针变量 cur沿着 next指针移动到倒数第 2 个链节点。
2. 然后将此节点的 next指针指向 None 即可

 // 从链表尾部删除元素removeRear() {if (!this.head || !this.head.next) {return 'Error'; // 链表为空或只有一个节点时，返回错误消息}let cur = this.head; // 从头节点开始遍历while (cur.next.next) {cur = cur.next; // 移动到倒数第二个节点}cur.next = null; // 将倒数第二个节点的 next 指向 null，实现删除尾部元素}

5.3. 链表中间删除元素

1. 先使用指针变量 cur移动到第 i−1 个位置的链节点。
2. 然后将 cur的 next指针，指向要第 i个元素的下一个节点即可

// 从链表中间删除元素removeInside(index) {let count = 0;let cur = this.head;while (cur.next && count < index - 1) {count++;cur = cur.next; // 移动到待删除元素的前一个节点}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}const delNode = cur.next; // 待删除的节点cur.next = delNode.next; // 将前一个节点的 next 指向待删除节点的下一个节点，实现删除中间元素}

6. 代码总结

  // 链表节点类class ListNode {constructor(value) {this.value = value; // 节点的值this.next = null;  // 下一个节点的引用}}// 链表类class LinkedList {constructor(data = []) {this.head = null; // 链表的头节点if (data.length > 0) {this.create(data); // 如果传入了数组，则自动初始化链表}}// 创建链表create(data) {this.head = new ListNode(0); // 创建一个带有虚拟头节点的链表let cur = this.head; // 初始化当前节点为头节点for (let i = 0; i < data.length; i++) {const node = new ListNode(data[i]); // 创建新的节点cur.next = node; // 将当前节点的 next 指向新节点cur = cur.next; // 更新当前节点为新节点，继续下一个循环}}// 获取链表的长度length() {let count = 0;let cur = this.head; // 从头节点开始遍历while (cur) {count++; // 增加计数器cur = cur.next; // 移动到下一个节点}return count; // 返回链表的长度}// 查找链表中具有特定值的元素find(val) {let cur = this.head; // 从头节点开始遍历while (cur) {if (val === cur.value) {return cur; // 如果找到值等于 val 的元素，返回该元素}cur = cur.next; // 否则继续遍历下一个节点}return null; // 如果没有找到匹配元素，返回 null}// 在链表头部插入元素insertFront(val) {const node = new ListNode(val); // 创建新节点node.next = this.head; // 将新节点的 next 指向原头节点this.head = node; // 更新头节点为新节点}// 在链表尾部插入元素insertRear(val) {const node = new ListNode(val); // 创建新节点let cur = this.head; // 从头节点开始遍历while (cur.next) {cur = cur.next; // 移动到下一个节点，直到找到最后一个节点}cur.next = node; // 将最后一个节点的 next 指向新节点，实现插入}// 在链表中指定位置插入元素insertInside(index, val) {let count = 0;let cur = this.head;while (cur && count < index - 1) {count++;cur = cur.next;}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}const node = new ListNode(val); // 创建新节点node.next = cur.next; // 将新节点的 next 指向当前节点的下一个节点cur.next = node; // 更新当前节点的 next，实现插入}// 更改链表中第 i 个元素的值为 valchange(index, val) {let count = 0;let cur = this.head; // 从头节点开始遍历while (cur && count < index) {count++; // 增加计数器cur = cur.next; // 移动到下一个节点}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}cur.value = val; // 更改指定位置的元素的值为 val}// 从链表头部删除元素removeFront() {if (this.head) {this.head = this.head.next; // 将头节点更新为下一个节点，实现删除头部元素}}// 从链表尾部删除元素removeRear() {if (!this.head || !this.head.next) {return 'Error'; // 链表为空或只有一个节点时，返回错误消息}let cur = this.head; // 从头节点开始遍历while (cur.next.next) {cur = cur.next; // 移动到倒数第二个节点}cur.next = null; // 将倒数第二个节点的 next 指向 null，实现删除尾部元素}// 从链表中间删除元素removeInside(index) {let count = 0;let cur = this.head;while (cur.next && count < index - 1) {count++;cur = cur.next; // 移动到待删除元素的前一个节点}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}const delNode = cur.next; // 待删除的节点cur.next = delNode.next; // 将前一个节点的 next 指向待删除节点的下一个节点，实现删除中间元素}}

三、题目练习

1. 翻转链表

给你链表的头节点 head ，请你反转链表，并返回反转后的链表

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用

 reverse() {let prev = null;let current = this.head;let next = null;while (current !== null) {next = current.next; // 保存下一个节点的引用current.next = prev; // 当前节点的 next 指向前一个节点，实现反转prev = current; // 移动前一个节点指针current = next; // 移动当前节点指针}this.head = prev; // 更新链表头部为反转后的链表头部}

2. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

具体地，我们从指针 cur指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与 cur.next对应的元素相同，那么我们就将 cur.next从链表中移除；否则说明链表中已经不存在其它与 cur对应的元素相同的节点，因此可以将 cur指向 cur.next。

当遍历完整个链表之后，我们返回链表的头节点即可

// 删除链表中重复的元素
removeDuplicates() {let current = this.head; // 从链表头部开始遍历while (current !== null && current.next !== null) {if (current.value === current.next.value) {current.next = current.next.next; // 删除重复元素，将当前节点的 next 指向下下一个节点} else {current = current.next; // 移动到下一个节点，继续遍历}}
}

四、链表排序

在数组排序中，常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。

而对于链表排序而言，因为链表不支持随机访问，访问链表后面的节点只能依靠 next 指针从头部顺序遍历，所以相对于数组排序问题来说，链表排序问题会更加复杂一点。

1. 适合链表的排序算法

• ：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。

2. 不适合链表的排序算法

• 希尔排序。

2.1. 希尔排序为什么不适合链表排序？

希尔排序中经常涉及到对序列中第 i + gap 的元素进行操作，其中 gap 是希尔排序中当前的步长。而链表不支持随机访问的特性，导致这种操作不适合链表，因而希尔排序算法不适合进行链表排序

我们主要来学习一下链表的插入排序和归并排序

3. 链表插入排序

3.1. 思路

1. 先使用哑节点 dummy_head 构造一个指向 head 的指针，使得可以从 head 开始遍历。
2. 维护 sorted_list 为链表的已排序部分的最后一个节点，初始时，sorted_list = head。
3. 维护 prev 为插入元素位置的前一个节点，维护 cur 为待插入元素。初始时，prev = head，cur = head.next。
4. 比较 sorted_list 和 cur 的节点值。

• 如果 sorted_list.val <= cur.val，说明 cur 应该插入到 sorted_list 之后，则将 sorted_list 后移一位。
• 如果 sorted_list.val > cur.val，说明 cur 应该插入到 head 与 sorted_list 之间。则使用 prev 从 head 开始遍历，直到找到插入 cur 的位置的前一个节点位置。然后将 cur 插入。

1. 令 cur = sorted_list.next，此时 cur 为下一个待插入元素。
2. 重复 4、5 步骤，直到 cur 遍历结束为空。返回 dummy_head 的下一个节点

3.2. 代码

  // 链表节点类class ListNode {constructor(value) {this.value = value; // 节点的值this.next = null;  // 下一个节点的引用}}// 链表类class LinkedList {constructor(data = []) {this.head = null; // 链表的头节点if (data.length > 0) {this.create(data); // 如果传入了数组，则自动初始化链表}}// 创建链表create(data) {this.head = new ListNode(0); // 创建一个带有虚拟头节点的链表let cur = this.head; // 初始化当前节点为头节点for (let i = 0; i < data.length; i++) {const node = new ListNode(data[i]); // 创建新的节点cur.next = node; // 将当前节点的 next 指向新节点cur = cur.next; // 更新当前节点为新节点，继续下一个循环}}// 获取链表的长度length() {let count = 0;let cur = this.head; // 从头节点开始遍历while (cur) {count++; // 增加计数器cur = cur.next; // 移动到下一个节点}return count; // 返回链表的长度}// 查找链表中具有特定值的元素find(val) {let cur = this.head; // 从头节点开始遍历while (cur) {if (val === cur.value) {return cur; // 如果找到值等于 val 的元素，返回该元素}cur = cur.next; // 否则继续遍历下一个节点}return null; // 如果没有找到匹配元素，返回 null}// 在链表头部插入元素insertFront(val) {const node = new ListNode(val); // 创建新节点node.next = this.head; // 将新节点的 next 指向原头节点this.head = node; // 更新头节点为新节点}// 在链表尾部插入元素insertRear(val) {const node = new ListNode(val); // 创建新节点let cur = this.head; // 从头节点开始遍历while (cur.next) {cur = cur.next; // 移动到下一个节点，直到找到最后一个节点}cur.next = node; // 将最后一个节点的 next 指向新节点，实现插入}// 在链表中指定位置插入元素insertInside(index, val) {let count = 0;let cur = this.head;while (cur && count < index - 1) {count++;cur = cur.next;}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}const node = new ListNode(val); // 创建新节点node.next = cur.next; // 将新节点的 next 指向当前节点的下一个节点cur.next = node; // 更新当前节点的 next，实现插入}// 更改链表中第 i 个元素的值为 valchange(index, val) {let count = 0;let cur = this.head; // 从头节点开始遍历while (cur && count < index) {count++; // 增加计数器cur = cur.next; // 移动到下一个节点}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}cur.value = val; // 更改指定位置的元素的值为 val}// 从链表头部删除元素removeFront() {if (this.head) {this.head = this.head.next; // 将头节点更新为下一个节点，实现删除头部元素}}// 从链表尾部删除元素removeRear() {if (!this.head || !this.head.next) {return 'Error'; // 链表为空或只有一个节点时，返回错误消息}let cur = this.head; // 从头节点开始遍历while (cur.next.next) {cur = cur.next; // 移动到倒数第二个节点}cur.next = null; // 将倒数第二个节点的 next 指向 null，实现删除尾部元素}// 从链表中间删除元素removeInside(index) {let count = 0;let cur = this.head;while (cur.next && count < index - 1) {count++;cur = cur.next; // 移动到待删除元素的前一个节点}if (!cur) {return 'Error'; // 如果未找到指定位置，返回错误消息}const delNode = cur.next; // 待删除的节点cur.next = delNode.next; // 将前一个节点的 next 指向待删除节点的下一个节点，实现删除中间元素}// 删除链表中重复的元素removeDuplicates() {let current = this.head;while (current !== null && current.next !== null) {if (current.value === current.next.value) {current.next = current.next.next; // 删除重复元素} else {current = current.next;}}}}class Solution {// 插入排序方法insertionSort(head) {const dummy_head = new ListNode(0); // 创建一个哑节点dummy_head.next = head; // 哑节点指向原链表头let sorted_list = head; // 初始化已排序部分的最后一个节点let prev = head; // 初始化 prev 为插入元素位置的前一个节点let cur = head.next; // 初始化 cur 为待插入元素while (cur) {// 如果 sorted_list 的值小于等于 cur 的值，继续向后移动if (sorted_list.value <= cur.value) {sorted_list = sorted_list.next;} else {// 如果 sorted_list 的值大于 cur 的值，从头到 sorted_list 之间找到插入位置的前一个节点prev = dummy_head;while (prev.next.value <= cur.value) {prev = prev.next;}// 插入 cur 到 prev 和 prev.next 之间sorted_list.next = cur.next; // 将 cur 从原位置删除cur.next = prev.next; // 将 cur 插入到 prev 和 prev.next 之间prev.next = cur;cur = sorted_list.next; // 移动到下一个待插入元素}}return dummy_head.next; // 返回排序后的链表}
}const a = new LinkedList([5, 1, 9, 3, 4])const solution = new Solution()solution.bubbleSort(a.head)console.log(a)

4. 链表归并排序

4.1. 思路

1. 分割环节：找到链表中心链节点，从中心节点将链表断开，并递归进行分割。

• 使用快慢指针 fast = head.next、slow = head，让 fast 每次移动 2 步，slow 移动 1 步，移动到链表末尾，从而找到链表中心链节点，即 slow。
• 从中心位置将链表从中心位置分为左右两个链表 left_head 和 right_head，并从中心位置将其断开，即 slow.next = None。
• 对左右两个链表分别进行递归分割，直到每个链表中只包含一个链节点。

1. 归并环节：将递归后的链表进行两两归并，完成一遍后每个子链表长度加倍。重复进行归并操作，直到得到完整的链表。

• 使用哑节点 dummy_head 构造一个头节点，并使用 cur 指向 dummy_head 用于遍历。
• 比较两个链表头节点 left 和 right 的值大小。将较小的头节点加入到合并后的链表中，并向后移动该链表的头节点指针。
• 然后重复上一步操作，直到两个链表中出现链表为空的情况。
• 将剩余链表插入到合并后的链表中。
• 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为合并后的头节点返回

4.2. 代码

class Solution {// 归并排序方法mergeSort(head) {if (!head || !head.next) {return head; // 如果链表为空或只有一个节点，返回链表本身}// 分割环节：找到链表中心链节点let mid = this.findMiddle(head);let left_head = head;let right_head = mid.next;mid.next = null;// 递归分割左右两个链表left_head = this.mergeSort(left_head);right_head = this.mergeSort(right_head);// 归并环节：合并左右两个链表return this.merge(left_head, right_head);}// 找到链表中心链节点findMiddle(head) {if (!head) {return null;}let slow = head;let fast = head.next;while (fast && fast.next) {slow = slow.next;fast = fast.next.next;}return slow;}// 合并两个链表merge(left, right) {let dummy_head = new ListNode(0); // 创建一个哑节点let cur = dummy_head; // 使用 cur 遍历while (left && right) {if (left.value < right.value) {cur.next = left;left = left.next;} else {cur.next = right;right = right.next;}cur = cur.next;}// 将剩余链表插入到合并后的链表中cur.next = left || right;return dummy_head.next;}
}

——未完待续——