JavaScript 链表定义与使用方法示例

JavaScript 链表定义与使用方法示例攻略

链表是一种常用的数据结构，它由多个节点组成，每个节点包含一个值和指向下一个节点的指针。这篇文章将会详细介绍JavaScript中链表的定义方法以及常用的链表操作方法。

定义链表

在JavaScript中，我们可以使用对象来定义一个链表。一个链表节点可以用一个对象来描述，该对象至少应该包含一个值val和一个指向下一个节点的指针next。链表的头节点可以用一个变量来表示，初始值为null。

// 定义链表节点
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 定义链表头节点
let head = null;

插入节点

插入节点是链表的一个常用操作，可以在任意位置插入一个节点。假设我们要在链表的第2个位置插入一个值为3的节点，实现方法如下：

// 定义节点
const newNode = new ListNode(3);

// 插入节点
if (!head) { // 特判链表为空
  head = newNode;

} else {
  let prev = null; // 定义前一个节点
  let cur = head; // 定义当前节点
  let count = 1; // 计数器

  while (count < 2) { // 找到要插入的位置
    prev = cur;
    cur = cur.next;
    count++;
  }

  prev.next = newNode; // 插入节点
  newNode.next = cur;
}

删除节点

删除指定节点是链表的另一个常用操作。假设我们要删除链表中第3个位置的节点，实现方法如下：

if (!head) { // 特判链表为空
  return null;
}

let prev = null; // 定义前一个节点
let cur = head; // 定义当前节点
let count = 1; // 计数器

while (count < 3) { // 找到要删除的位置
  prev = cur;
  cur = cur.next;
  count++;
}

prev.next = cur.next; // 删除节点

示例说明1：反转链表

反转链表也是一个常规操作，假设我们有一个链表是1->2->3->4->null，现在要求将它反转为4->3->2->1->null。实现方法如下：

// 定义链表节点
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 定义链表头节点
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);

// 反转链表
let prev = null;
let cur = head;

while (cur) {
  let nextNode = cur.next;
  cur.next = prev;
  prev = cur;
  cur = nextNode;
}

head = prev;

console.log(head); // 4->3->2->1->null

示例说明2：链表中的环

在一个链表中，每个节点的指针都指向下一个节点，但是在某些情况下，一个节点的指针会指向前面的某个节点，从而形成环。如何判断一个链表中是否存在环呢？假定我们有一个链表是1->2->3->2->4，现在要求判断它是否存在环。实现方法如下：

// 定义链表节点
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 定义链表头节点
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = head.next;

// 判断链表中是否存在环
let slow = head;
let fast = head;

while (slow && fast && fast.next) {
  slow = slow.next;
  fast = fast.next.next;

  if (slow === fast) {
    console.log("存在环");
    break;
  }
}

if (slow !== fast) {
  console.log("不存在环");
}

以上是JavaScript中链表的定义与应用方法示例攻略，通过此攻略可以了解链表操作的基本方法，并且可以应用于实际开发中。