HOW - 链表系列（一）

一、JavaScript 中的链表

在JavaScript中，链表并不像在某些其他编程语言中那样常见。这是因为JavaScript中的数组（Array）数据结构通常能够满足大多数数据存储和操作的需求，而且更加方便和易用。

以下是一些可能导致JavaScript中较少使用链表的原因：

数组的灵活性：JavaScript中的数组是动态的，并且可以根据需要自动调整大小。这使得数组在存储和访问元素时非常方便，并且支持随机访问，即可以通过索引直接访问任意位置的元素。
内存管理：JavaScript中的内存管理是由垃圾收集器（Garbage Collector）自动处理的，它负责分配和释放内存。而链表在插入和删除节点时需要手动管理内存，需要考虑节点的创建和销毁，更容易出现内存泄漏等问题。
缺乏指针操作：JavaScript是一种高级语言，它的设计目标是提供简单易用的编程体验。与低级语言相比，JavaScript缺乏直接的指针操作，这使得链表的实现和操作变得相对复杂和笨重。

尽管如此，链表在一些特定的应用场景下仍然有其优势。例如，当需要频繁进行插入和删除操作而不关心随机访问时，链表可能更适合。此外，一些算法和数据结构问题也需要使用链表进行解决。

虽然JavaScript中链表的使用相对较少，但了解链表的概念和实现方式仍然是有益的，因为它们在计算机科学中是一种重要的数据结构，并广泛应用于其他编程语言和算法领域。

二、链表

关于链表的基础内容这里不进行介绍，我们将通过一些经典场景来学习和掌握链表相关操作。

移除链表元素

删除链表中等于给定值 val 的所有节点。

示例 1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2：输入：head = [], val = 1 输出：[]

示例 3：输入：head = [7,7,7,7], val = 7 输出：[]

// 定义链表节点类
class ListNode {constructor(val, next) {this.val = val;this.next = next || null;}
}
// 创建链表
const head = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);
let node5 = new ListNode(5);
head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;var removeElements = function(head, val) {// 推荐定义一个额外的虚拟头节点，可以保证真实头节点和后续的普通节点用同一个操作逻辑const ret = new ListNode(0, head);let cur = ret;while(cur.next) {if(cur.next.val === val) {cur.next =  cur.next.next;continue;}cur = cur.next;}return ret.next;
};
removeElements(head, 4);
console.log(head);

反转链表

反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的 next 指针的指向，直接将链表反转，而不用重新定义一个新的链表。

1. 双指针法

思路：首先定义一个 cur 指针，指向头结点，再定义一个 pre 指针，初始化为 null。

然后就要开始反转了，首先要把 cur->next 节点用 tmp 指针保存一下，也就是保存一下这个节点。为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将 cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动 pre 和 cur 指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们 return pre 指针就可以了，pre 指针就指向了新的头结点。

// 定义链表节点类
class ListNode {constructor(val, next) {this.val = val;this.next = next || null;}
}
// 创建链表
const head = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);
let node5 = new ListNode(5);
head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;// 反转链表
let newHead = reverseLinkedList(head);
function reverseLinkedList(head) {let pre = null;let cur = head;while (cur) {let temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;
}console.log(newHead);

时间复杂度: O(n)，空间复杂度: O(1)。

2. 递归法1：从前往后翻转指针指向

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当 cur 为空的时候循环结束，不断将 cur 指向 pre 的过程。关键是初始化的地方，从下方代码实现可以看到双指针法中初始化 cur = head, pre = NULL，在递归法中初始化的逻辑也是一样的，只不过写法变了。

// 定义链表节点类
class ListNode {constructor(val, next) {this.val = val;this.next = next || null;}
}
// 创建链表
const head = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);
let node5 = new ListNode(5);
head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;// 反转链表
var reverse = function(pre, head) {if(!head) return pre;const temp = head.next;head.next = pre;pre = head;return reverse(pre, temp); // cur=temp; pre=cur;
}
var reverseLinkedList = function(head) {return reverse(null, head); // 初始化
};
const newHead = reverseLinkedList(head);console.log(newHead);

时间复杂度: O(n), 要递归处理链表的每个节点，空间复杂度: O(n), 递归调用了 n 层栈空间。

3. 递归法2：从后往前翻转指针指向

// 定义链表节点类
class ListNode {constructor(val, next) {this.val = val;this.next = next || null;}
}
// 创建链表
const head = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);
let node5 = new ListNode(5);
head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;// 反转链表
var reverse = function(head) {if(!head || !head.next) return head;// 从后往前翻console.log(head.val);const pre = reverse(head.next);console.log(pre.val);head.next = pre.next;pre.next = head;return head;
}
var reverseLinkedList = function(head) {let cur = head;while(cur && cur.next) {cur = cur.next;}// 反转reverse(head);// 找到最后一个节点并作为最后的返回值return cur;
};
const newHead = reverseLinkedList(head);console.log(newHead);//> "head.val" 1
//> "head.val" 2
//> "head.val" 3
//> "head.val" 4
//> "pre.val" 5
//> "pre.val" 4
//> "pre.val" 3
//> "pre.val" 2
//> [object Object]