1. 认识链表

链表是一种通过指针的形式把一组存储单元联系在一起的数据结构。
js 中没有链表，但可以用 Object 模拟链表
链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客（类似于数据），并且这个节点会连接下一个节点，以此类推

链表的火车结构：

链表的常见操作：
1. append(element)：向链表尾部添加一个新的项
2. insert(value, position)：向链表的特定位置插入一个新的项
3. get(position)：获取对应位置的元素
4. indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回 -1
5. update(position,element)：修改某个位置的元素
6. removeAt(postion)：从链表的特定位置移除一项
7. remove(element)：从链表中移除一项
8. isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于等于0返回false
9. size()：返回链表包含的元素个数。与数组的length属性类似

2. 实现链表结构的封装

2.1 基础框架 v1 版

ts
// 1. 创建 Node 节点类
class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

// 2. 创建 LinkedList 的类
class LinkedList<T> {
  private head: Node<T> | null = null;
  private size: number = 0;

  get length() {
    return this.size;
  }
}

代码解析：

封装一个 Node 类，用于封装每一个节点上的信息（包括和指向下一个节点的引用），它是一个泛型类
封装一个 LinkedList 类，用于表示链表结构
链表中保存两个属性，
1. size：链表长度
2. head：链表中的第一个节点

基础的框架搭建好了，我们接下来就来一个个添加方法

2.2 添加 append 方法 v2 版

向 LinkedList 添加 append(element) 方法

append 方法的作用是向链表尾部添加一个新的项

ts
  append(value: T) {
    // 1. 根据 value创建一个新节点
    const newNode = new Node(value)

    // 2. 判断 this.head 是否为 null
    if(!this.head) {
      this.head = newNode
    } else {
      let current = this.head
      while(current.next) {
        current = current.next
      }

      // 此时 current 指向最后一个节点
      current.next = newNode 
    }

    // 3. size++
    this.size++
  }

2.3 添加 traverse 方法 v3 版

为了方便可以看到链表上的每一个节点，我们实现一个 traverse 方法

向 LinkedList 添加 traverse 方法

traverse 方法的作用是 遍历链表

ts
  traverse() {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }

    console.log(values.join("->"));
  }

测试：

ts
const l = new LinkedList<string>();
l.append("第一个节点");
l.append("第二个节点");
l.append("第三个节点");
l.traverse();  // 第一个节点->第二个节点->第三个节点

2.4 添加 insert 方法 v4 版

向 LinkedList 添加 insert(value, position) 方法

insert方法的作用是向链表的特定位置插入一个新的项

ts
  insert(value: T, position: number): boolean {
    // 1. 越界判断
    if (position < 0 || position >= this.size) return false;

    // 2. 根据 value 创建新的节点
    const newNode = new Node(value);

    // 3. 判断是否需要插入头部
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let current = this.head;
      let previous: Node<T> | null = null;
      let index = 0;

      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }

      // index === position
      newNode.next = current;
      previous!.next = newNode;
    }
    return true;
  }

测试：

ts
const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");

// l.insert("ddd", 0); // 插入头部位置 ddd->aaa->bbb->ccc
// l.insert("ddd", 2); // 插入第二个位置  aaa->bbb->ddd->ccc
// l.insert("ddd", 3); // 插入尾部 aaa->bbb->ccc->ddd

l.traverse();

2.5 添加 removeAt 方法 v5 版

向 LinkedList 添加 removeAt(postion) 方法

removeAt方法的作用是从链表的特定位置移除一项

ts
  removeAt(position: number): T | null {
    // 1. 越界判断
    if (position < 0 || position > this.size) return null;

    // 2. 判断是否删除第一个节点
    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;
    } else {
      let previous: Node<T> | null = null;
      let index = 0;

      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }
      previous!.next = current?.next ?? null;
    }

    this.size--;

    return current?.value ?? null;
  }

测试：

ts
const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");

// console.log(l.removeAt(0)); // aaa
// console.log(l.removeAt(1)); // bbb
// console.log(l.removeAt(2)); // ccc
// console.log(l.removeAt(3)); // null

l.traverse();

2.6 添加 get 方法 v6 版

向 LinkedList 添加 get(postion) 方法

get方法的作用是获取对应位置的元素

ts
  get(position: number): T | null {
    // 越界问题
    if (position < 0 || position >= this.size) return null;

    // 2. 查找元素
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }

    // index === position
    return current?.value ?? null;
  }

测试：

ts
const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");

console.log(l.get(0)); // aaa
console.log(l.get(1)); // bbb
console.log(l.get(2)); // ccc
console.log(l.get(3)); // null

2.7 添加 getNode 方法 v7 版

到这里，我们发现上面的代码在 通过 position 获取节点的逻辑 上有很多重复的地方，现在我们通过添加 getNode 方法来重构一下

向 LinkedList 添加 getNode(postion) 私有方法

getNode方法的作用是获取对应位置的节点

ts
  // 封装私有方法
  // 根据 position 获取得到当前的节点
  private getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    return current;
  }

有了这个方法，我们就可以对 get removeAt insert 方法进行重构了

对 removeAt 进行重构

diff
  removeAt(position: number): T | null {
    // 1. 越界判断
    if (position < 0 || position > this.size) return null;

    // 2. 判断是否删除第一个节点
    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;
    } else {
-      let previous: Node<T> | null = null;
-      let index = 0;
-
-      while (index++ < position && current) {
-        previous = current;
-        current = current.next;
-      }
-      previous!.next = current?.next ?? null;
+      let previous = this.getNode(position - 1);
+      current = previous?.next ?? null;
+      previous!.next = previous?.next?.next ?? null;
    }

    this.size--;

    return current?.value ?? null;
  }

对 get 进行重构

diff
  get(position: number): T | null {
    // 越界问题
    if (position < 0 || position >= this.size) return null;

    // 2. 查找元素
-    let index = 0;
-    let current = this.head;
-    while (index++ < position && current) {
-      current = current?.next;
-    }
+    let current = this.getNode(position);

    return current?.value ?? null;
  }

对 insert 进行重构

diff
  insert(value: T, position: number): boolean {
    // 1. 越界判断
    if (position < 0 || position > this.size) return false;

    // 2. 根据 value 创建新的节点
    const newNode = new Node(value);

    // 3. 判断是否需要插入头部
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
-      let current = this.head;
-      let previous: Node<T> | null = null;
-      let index = 0;
-
-      while (index++ < position && current) {
-        previous = current;
-        current = current.next;
-      }
-
-      // index === position
-      newNode.next = current;
-      previous!.next = newNode;
+      const previous = this.getNode(position - 1);
+      newNode.next = previous?.next ?? null;
+      previous!.next = newNode;
    }
    return true;
  }

测试一把，都没问题

ts
const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");

// console.log(l.removeAt(0)); // aaa
// console.log(l.removeAt(1)); // bbb
// console.log(l.removeAt(2)); // ccc
// console.log(l.removeAt(3)); // null

// console.log(l.get(0)) // aaa
// console.log(l.get(1)) // bbb
// console.log(l.get(2)) // ccc
// console.log(l.get(3)) // null

// l.insert("ddd", 0); // ddd->aaa->bbb->ccc
// l.insert("ddd", 1); // aaa->ddd->bbb->ccc
// l.insert("ddd", 2); // aaa->bbb->ddd->ccc
// l.insert("ddd", 3); // aaa->bbb->ccc->ddd
// l.insert("ddd", 4); // aaa->bbb->ccc
l.traverse();

2.8 添加 update 方法 v8 版

向 LinkedList 添加 update(position,element) 方法

update方法的作用是修改某个位置的元素

ts
  update(value: T, position: number):boolean {
    if (position < 0 || position >= this.size) return false;

    // 获取对应位置的节点，直接更新即可
    const currentNode = this.getNode(position)
    currentNode!.value = value
    return true
  }

测试：

ts
const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");

l.traverse(); // aaa->bbb->ccc
l.update("ddd", 1); // aaa->ddd->ccc
l.traverse();

2.9 添加 indexOf 方法 v9 版

向 LinkedList 添加 indexOf(element) 方法

indexOf方法的作用是返回元素在链表中的索引。如果链表中没有该元素则返回 -1

ts
  indexOf(value: T) {
    // 从第一个节点开始，向后遍历
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

测试：

ts
const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");

console.log(l.indexOf("aaa"));
console.log(l.indexOf("bbb"));
console.log(l.indexOf("ccc"));

2.10 添加 remove 方法 v10 版

向 LinkedList 添加 remove(element) 方法

remove方法的作用是从链表中移除一项

ts
  remove(value: T): T | null {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }

测试：

ts
const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");

l.remove('bbb')
l.traverse() // aaa->ccc

2.11 添加方法 isEmpty v11 版

向 LinkedList 添加 isEmpty() 方法

isEmpty方法的作用是如果链表中不包含任何元素，返回 true，如果链表长度大于等于 0 返回 false

ts
  isEmpty(): boolean {
    return this.size === 0;
  }

3. 面试题一：设计链表

这是 Leetcode 上的第 707 道题，难度为：中等

3.1 题目描述

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：


MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
get, addAtHead, addAtTail, addAtIndex 和 deleteAtIndex 的操作次数不超过 2000。

3.2 解答

这道题的答案在第二章就已经给出了，我们只需要进行一些修改即可

ts
class Node {
  value: number;
  next: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class MyLinkedList {
  private head: Node | null = null;
  private size: number = 0;

  constructor() {}

  private getNode(position: number): Node | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    return current;
  }

  get(index: number): number {
    if (index < 0 || index >= this.size) return -1;

    let current = this.getNode(index);

    return current!.value;
  }

  addAtHead(val: number): void {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.size++;
  }

  addAtTail(val: number): void {
    const newNode = new Node(val);

    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.getNode(this.size - 1);

      current!.next = newNode;
    }
    this.size++;
  }

  addAtIndex(index: number, val: number): void {
    if (index > this.size) return;

    if (index <= 0) {
      this.addAtHead(val);
    } else {
      const newNode = new Node(val);
      const previous = this.getNode(index - 1);
      newNode.next = previous?.next ?? null;
      previous!.next = newNode;
    }
    this.size++;
  }

  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;

    let current = this.head;

    if (index === 0) {
      this.head = current?.next ?? null;
    } else {
      const previous = this.getNode(index - 1);
      previous!.next = previous?.next?.next ?? null;
    }
    this.size--;
  }

}

复杂度分析：

时间复杂度：
1. 初始化消耗 O(1)
2. get 消耗 O(index)
3. addAtHead 消耗 O(1)
4. addAtTail 消耗 O(n)，其中 n 为链表当前长度
5. addAtIndex 消耗 O(index)
6. deleteAtIndex 消耗 O(index - 1)
空间复杂度：所有函数的单词调用空间复杂度均为 O(1)，总体空间复杂度为 O(n)，

4. 面试题二：删除链表中的节点

这是 Leetcode 上的第 237 道题，难度为：中等

4.1 题目描述

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。

自定义测试：

对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
我们将构建链表，并将节点传递给你的函数。
输出将是调用你函数后的整个链表。

示例 1：


输入： head = [4,5,1,9], node = 5
输出： [4,1,9]
解释： 指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：


输入： head = [4,5,1,9], node = 1
输出： [4,5,9]
解释： 指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

提示：

链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是唯一的
需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

4.2 解答

删除节点的操作我们其实之前就已经实现了的，我们只要拿到要删除节点的前一个节点，将前一个节点的 next 指向要删除节点的下一个节点即可。但是这道题有一个问题就是，我们拿不到要删除前点的上一个节点。

思路：

我们可以将要删除的节点的值赋值成它的下一个节点就行了，这样就将问题从删除某个节点转换成了删除某个节点的后一个节点，这样的好处就是我们能拿到要删除节点的前一个节点。

ts
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify it in-place instead.
 */
function deleteNode(node: ListNode | null): void {
  node.val = node.next.val;
  node.next = node.next.next;
}

复杂度分析

时间复杂度：O(1)。
空间复杂度：O(1)。

目录

1. 认识链表

2. 实现链表结构的封装

2.1 基础框架 v1 版

2.2 添加 append 方法 v2 版

2.3 添加 traverse 方法 v3 版

2.4 添加 insert 方法 v4 版

2.5 添加 removeAt 方法 v5 版

2.6 添加 get 方法 v6 版

2.7 添加 getNode 方法 v7 版

2.8 添加 update 方法 v8 版

2.9 添加 indexOf 方法 v9 版

2.10 添加 remove 方法 v10 版

2.11 添加方法 isEmpty v11 版

3. 面试题一：设计链表

3.1 题目描述

3.2 解答

4. 面试题二：删除链表中的节点

4.1 题目描述

4.2 解答