[JavaScript 刷题] 链表II，翻转链表，搜索，按值删除

• • Node
  • 构造函数
  • isEmpty
  • 插入实现
  • • 头插
    • 尾插
    • 中间插入
  • 搜索
  • 删除
  • • 头删
    • 尾删
    • 中间删除
    • 按值删除
  • 获取长度
  • 翻转链表
  • 其余有趣的实现

以单链表的功能为主。

Node

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

构造函数

class LinkedList {
  constructor() {
    this.head = null;
  }
}

isEmpty

判断链表是否为空，可以通过直接判断 head 是否为 null 进行实现。

时间复杂度为 O ( 1 ) O(1) O(1)

class LinkedList {
  // 省略其他实现

  isEmpty() {
    return this.head === null;
  }
}

插入实现

总共有三种：

• 在头部插入，insertAtHead()
• 在尾部插入，insertAtTail()
• 在指定索引插入，insertAtTail()

头插

直接新建一个新的 Node，将链表原本的 Head 指向新的 Node，将链表的 Head 指向新的 Node。

时间复杂度为 O(1)

图解如下：

1. 原本的链表

   2 为原本的 Head

2. 新建一个 Node 作为需要插入到链表头部的 Node。

3. 将原本的 Node 2 链接到新建的 Node 1 后

4. 更新链表的 Head

class LinkedList {
  // 省略其他实现

  insertAtHead(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
  }
}

尾插

根据接受的参数创一个新的 Node，随后找到链表最后一个结点，更新最后一个结点的 next。

时间复杂度为 O ( n ) O(n) O(n)，找到最后一个结点需要遍历整个链表。

class LinkedList {
  // 省略其他实现

  insertAtTail(data) {
    const newNode = new Node(data);

    if (this.isEmpty()) {
      return this.insertAtHead(data);
    }

    let curr = this.head;

    while (curr.nextElement !== null) {
      curr = curr.nextElement;
      console.log(curr);
    }

    curr.nextElement = newNode;
  }
}

中间插入

其实会了头插和尾差，在中间插入的实现就很简单了。

主要还是当索引在中间阶段的时候，需要断开原本结点之间的回路，并且创立新的回路：

2 --> 4 中的回路会断开，转而会变成 2 --> 3 --> 4：

最差情况下会使用尾差，所以这也是一个 O ( n ) O(n) O(n) 的操作。

class LinkedList {
  // 省略其他实现

  insertAt(index, data) {
    const newNode = new Node(data);

    // 当往头部插入，或者链表为空时，可以直接调用已经实现的函数
    if (index === 0 || this.isEmpty()) return this.insertAtHead(data);

    let curr = this.head,
      count = 1;

    while (curr.nextElement !== null && count < index) {
      count++;
      curr = curr.nextElement;
    }

    // 这里当插入的数据大于链表的长度时，直接选择在尾部插入。不过也可以通过抛出异常来提示错误
    if (count < index) return this.insertAtTail(data);

    const next = curr.nextElement;
    curr.nextElement = newNode;
    newNode.nextElement = next;
  }
}

搜索

搜索同样也是一个 O ( n ) O(n) O(n) 的操作，它需要完成对链表的遍历去寻找提供的值。

另外需要注意的是，搜索可以通过 遍历 和 递归的方式进行实现。便利查找的空间复杂度为 O ( 1 ) O(1) O(1)，而递归的空间复杂度为 O(n)。

class LinkedList {
  // 省略其他实现

  search(value) {
    let curr = this.head;

    while (curr !== null) {
      if (curr.value === value) return true;
      curr = curr.nextElement;
    }

    // 调用递归函数
    // this.recursiveSearch(this.head, value)

    return false;
  }

  recursiveSearch(node, value) {
    if (node === null) return false;
    if (node.value === value) return true;

    return this.recursiveSearch(node.nextElement, value);
  }
}

删除

和插入一样，删除也有几种不同的方式：

• 头删
• 尾删
• 中间删除
• 按值删除

头删

时间复杂度为 O ( 1 ) O(1) O(1)。

class LinkedList {
  // 省略其他实现

  deleteAtHead() {
    if (this.isEmpty()) return false;

    this.head = this.head.nextElement;
    return true;
  }
}

尾删

时间复杂度为 O ( n ) O(n) O(n)。

class LinkedList {
  // 省略其他实现

  deleteAtTail() {
    if (this.isEmpty()) return false;

    let curr = this.head;
    while (curr.nextElement.nextElement !== null) {
      curr = curr.nextElement;
    }

    curr.nextElement = null;

    return true;
  }
}

中间删除

时间复杂度为 O ( n ) O(n) O(n)。

class LinkedList {
  // 省略其他实现

  deleteAt(index) {
    if (this.isEmpty()) return false;

    let count = 1,
      curr = this.head;

    if (index === 0) return this.deleteAtHead();

    while (count < index && curr !== null) {
      curr = curr.nextElement;
      count++;
    }

    if (curr === null) return false;

    // 注意空值的问题
    curr.nextElement = curr.nextElement ? curr.nextElement.nextElement : null;
    return true;
  }
}

按值删除

其实还是搜索的逻辑，确认搜索的值是否是需要删除的值，随后再进行操作，时间复杂度为 O ( n ) O(n) O(n)。

class LinkedList {
  // 省略其他实现

  deleteBy(value) {
    if (this.isEmpty()) return false;

    let curr = this.head;
    if (curr.value === value) {
      this.head = curr.nextElement;
      return true;
    }

    while (curr.nextElement !== null) {
      if (curr.nextElement.value === value) {
        curr.nextElement = curr.nextElement.nextElement;
        return true;
      }
      curr = curr.nextElement;
    }

    return false;
  }
}

获取长度

有两种方式可以实现，第一种就是通过遍历的方式去获取链表的长度；第二种则是在保存一个链表长度的变量，每次操作的时候都需要更新这个变量。

这里就不修改之前已经写好的代码了，直接通过遍历的方式获取链表的长度，时间复杂度为 O ( n ) O(n) O(n)。

class LinkedList {
  // 省略其他实现
  length() {
    let length = 0;

    let curr = this.head;

    while (curr !== null) {
      length++;
      curr = curr.nextElement;
    }

    return length;
  }
}

翻转链表

本质上来说还是遍历链表，这个操作需要保留 3 个变量：prev, curr, next，交替更新。

原本的顺序为 prev -> curr -> next，在遍历到 curr 时需要进行通过 next 去保留地址，随后对 curr 和 prev 进行翻转操作，将其更新为 curr -> prev。一直到结束遍历，最后更新 this.head 即可。

时间复杂度为 O(n)

• 原链表

• 进入遍历，将 next 指向下一个结点，用以保留当前位置。同时反转 prev 和 curr

  此时链表本身的结构为：

• 更新 prev 和 curr 的位置

• 进入下一个遍历，更新 next 的指向

• 继续反转 curr 与 prev 之间的关系

  此时链表的结构为：

  可以看到，next 之前的结点已经实现了翻转。

• 继续重复这个过程一直到 curr 指向空

• 最后将 this.head 指向 prev，实现链表的翻转

class LinkedList {
  // 省略其他实现
  reverse() {
    let prev = null,
      curr = this.getHead(),
      next = null;

    while (curr !== null) {
      next = curr.nextElement;
      curr.nextElement = prev;
      prev = curr;
      curr = next;
    }

    this.head = prev;
  }
}

其余有趣的实现

也是一些常见的面试题，包括：

• 检查链表中是否存在环路 (双指针)
• 寻找链表中间的结点 (双指针)
• 移除链表中重复的数据 (哈希表)
• 寻找两个链表的并集和交集 (哈希表)
• 返回倒数第 N 个结点