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

2023-07-31 18:05:10

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

以单链表的功能为主。

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 3 Head null

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

    1 2 3 null Head null

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

    1 2 3 null Head

  4. 更新链表的 Head

    1 2 3 Head null 
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;
  }
}

中间插入

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

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

1 2 3 4 head null

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

断开 连接 连接 1 2 3 4 head null

最差情况下会使用尾差，所以这也是一个 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)

  • 原链表

    1 2 3 4 null null prev next curr head null

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

    1 2 3 4 null prev next curr head null

    此时链表本身的结构为：

    1 2 3 4 null head null

  • 更新 prev 和 curr 的位置

    1 2 3 4 null prev next curr head null

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

    1 2 3 4 null prev next curr head null

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

    1 2 3 4 null prev next curr head null

    此时链表的结构为：

    1 2 3 4 null head null

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

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

    1 2 3 4 null prev head null curr next

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

    1 2 3 4 null prev head null curr next 
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 个结点
上一篇：python – 检测并排除Pandas数据帧中的异常值


下一篇：【Datawhale第25期组队学习】Task04：基于相似度的方法