JavaScript is required

2025-11-25 关于链表(Javascript)

算法#数据结构#链表#JavaScript

关于链表(Javascript)

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用，在 JavaScript 中广泛应用于算法问题和实际开发

链表的基本操作

1. 单向链表的实现

下面是一个简单的单向链表的实现，包括节点定义和基本操作：

2. 双向链表的实现

下面是一个简单的双向链表的实现，包括节点定义和基本操作：

查找某个元素

问题描述：在链表中查找指定值的节点，并返回其位置索引。

javascript
/**
 * 查找指定值的节点
 * @param {LinkedList} list - 单向链表
 * @param {any} value - 要查找的值
 * @returns {number} - 节点的位置索引，如果未找到返回-1
 */
function findElement(list, value) {
  let current = list.head
  let index = 0

  while (current !== null) {
    if (current.value === value) {
      return index // 找到值，返回索引
    }
    current = current.next
    index++
  }

  return -1 // 未找到，返回-1
}

// 示例：查找元素
const searchList = new LinkedList()
searchList.append(1)
searchList.append(2)
searchList.append(3)
searchList.append(4)

console.log(findElement(searchList, 3)) // 输出 2
console.log(findElement(searchList, 5)) // 输出 -1
2. 在指定位置插入元素

问题描述：在链表的指定位置插入新节点。

3. 查找指定位置的元素

问题描述：获取链表中指定位置的元素值。

4. 删除指定位置的元素

问题描述：删除链表中指定位置的节点。

5. 获取链表长度

问题描述：计算链表中节点的数量。

javascript
/**
 * 获取链表长度
 * @param {LinkedList} list - 单向链表
 * @returns {number} - 链表长度
 */
function getListLength(list) {
  let current = list.head
  let length = 0

  while (current !== null) {
    length++
    current = current.next
  }

  return length
}

// 示例：获取链表长度
const lengthList = new LinkedList()
lengthList.append(1)
lengthList.append(2)
lengthList.append(3)

console.log(getListLength(lengthList)) // 输出 3
lengthList.append(4)
console.log(getListLength(lengthList)) // 输出 4

其他操作

  • 查找元素：根据值查找节点位置
  • 指定位置插入：在特定位置插入新节点
  • 指定位置获取：获取特定位置的节点值
  • 指定位置删除：删除特定位置的节点
  • 递归反转：使用递归方式反转链表
  • 获取长度：统计链表中节点的数量
反转链表

问题描述：反转一个单向链表

  • 初始化 prev 为 null（新链表的尾部）。
  • current 从链表头节点开始。
  • 在循环中：
  • 循环结束后，prev 指向原链表的尾节点（新头节点），更新 list.head = prev。

其实就是三指针原地反转

alt text

javascript
/**
 * 反转单向链表
 * @param {LinkedList} list - 单向链表
 * @returns {LinkedList} - 反转后的链表
 */
function reverseLinkedList(list) {
  let prev = null
  let current = list.head
  while (current !== null) {
    let next = current.next // 暂存下一个节点
    current.next = prev // 将当前节点的 next 指向前一个节点
    prev = current // 更新前一个节点为当前节点
    current = next // 继续遍历下一个节点
  }
  list.head = prev // 更新头节点为最后一个非空节点
  return list
}

// 示例：反转链表
const rList = new LinkedList()
rList.append(1)
rList.append(2)
rList.append(3)
rList.print() // 输出 1 -> 2 -> 3 -> null
reverseLinkedList(rList)
rList.print() // 输出 3 -> 2 -> 1 -> null
合并两个有序链表

问题描述：合并两个有序链表，使结果链表仍然有序。

更新中